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

• Markov Algorithm explained for SEO

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)

One more interpreter

There is one more interpreter of Markov Algorithm with a debugger: fvm2. Maybe add it to the external links? — Preceding unsigned comment added by 109.251.129.106 (talk) 11:50, 8 June 2013 (UTC)

Edits

I have just corrected many errors in grammar and usage. Inline citations still need to be added. I changed all instances of "word" to "string" so that the wording would be consistent. In the "another example" section, I also changed the order of the rules in the algorithm so that the steps would be correct, back to the original order (before the edit by 188.163.114.37). Either order has the same result, but the listed steps are only for this order. It seems that there is redundant information between the sections "Descripiton" and "Algorithm." Furthermore, it needs to be cleared up whether "Markov Algorithm" and "Normal Algorithm" are exactly synonymous. Finally, It would be helpful if someone changed the formatting in the Description and the examples so that they match.Dijekjapen (talk) 01:10, 16 May 2020 (UTC)