Talk:Markov algorithm
Moved form article page:
- Hello, Can anyone help me out with Markov Algorithm?
- Is it anything to do with a Markov chain?
No. 'Markov chains' come up in the study of stochastic processes. 'Markov algorithms' are the work of the son of the Markov of 'Markov chain' fame.
A.A. Markov (the elder) (1856-1922) http://www-groups.dcs.st-and.ac.uk/~history/Mathematicians/Markov.html
A.A. Markov (the younger) (1903-1979) http://logic.pdmi.ras.ru/Markov/
The younger Markov was a founder and leading member of what is often called the "Russian School of Constructive Mathematics". Descriptions of their ethos can be found in the introductions to Beeson and Trolestra/van Dalen (they seem to me to contradict each other though on some points).
Beeson, M.J., Foundations of constructive mathematics, Springer-Verlag 1985.
Troelstra, A.S and D. van Dalen, Constructivism in mathematics, an introduction, two volumes, North-Holland, 1988.
"The Russian school of constructive mathematics, initiated by A.A. Markov and continued by N.A. Shanin, G.S. Tseitin, B.A. Kushner and others, is probably best thought of as constructive recursive mathematics. The underlying logic is intuitionistic, but the mathematical objects are restricted to finite objects---including algorithms represented by finite strings of symbols. Historically, but perhaps not necessarily, this school adopted Markov's principle: to show that an algorithm halts at some stage, it suffices to prove that it cannot possibly run forever. Brouwer held Markov's principle to be false, and in certain formalizations of his thinking it is refutable. However, as it is classically true, it is not refutable in basic constructive mathematics." - Fred Richman, http://www.math.fau.edu/Richman/html/construc.htm
Examples
I thought of an example: a converter from Roman number into Arabic number (restricted to the interval of 0–99). I am not sure yet, all these things are new to me, thus I do not insert it yet to the article page.
It can be experimented with on the online Markov algorithm interpreter.
nihilum->.0 nihil->.0 nil->.0 XC->[90] IC->[99] LXXX->[80] LXX->[70] LX->[60] XL->[40] IL->[49] L->[50] XXX->[30] XX->[20] IX->[9] X->[10] VIII->[8] VII->[7] VI->[6] IV->[4] V->[5] III->[3] II->[2] I->[1] 0-> [-> ]->
Unfortunatelly, it does not illustrate the importance of the “after applying first matching rule, rerun the search” principle entirely (although it illustrates that the first rules have a precedence above later rules in some sense). Also an example of the importance of terminating rules is given by nil->.0 like rules.
I have not found yet a good illustration for the other seemingly strange (unnatural, arbitrary) principle (“only the leftmost is substituted in a match”). Superficially, it is similar to lazy evaluation (but I think, no deep connections exist, this is just an accident). But one can illustrate the importance of the “only the leftmost is substituted in a match” by the fact, that an “entire replacement in one match” rule would be no less arbitrary-looking. Because also such a principle would involve some arbitraryness: e.g. when applying
bab->7
rule in
babab
string, it would require a — necessarily arbitrary — resolution of overlapping occurrences.
Physis 11:05, 20 October 2006 (UTC)
Removed misleading link
I removed the link
which points to a page about Markov chains, not the Markov Algorithm. Jks 18:31, 28 November 2006 (UTC)
Other language examples
What about SNOBOL and Expect as other examples of languages using the Markov Algorithm paradigm? Jeremybennett (talk) 14:31, 30 April 2010 (UTC)