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 conversion. 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 on online Markov algorithm interpreter.

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

At least,it should exemplify the importance of the “after applying first matching rule, rerun the search” principle.