Talk:Markov algorithm

From Wikipedia, the free encyclopedia

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

[edit] 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