Talk:Markov algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Russia / Science & education (Rated Start-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Russia, a WikiProject dedicated to coverage of Russia on Wikipedia.
To participate: Feel free to edit the article attached to this page, join up at the project page, or contribute to the project discussion.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
Taskforce icon
This article is supported by the science and education in Russia task force.

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)

A.A. Markov (the younger) (1903-1979)

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,


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.


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


rule in


string, it would require a — necessarily arbitrary — resolution of overlapping occurrences.

Physis 11:05, 20 October 2006 (UTC)

Removed misleading link[edit]

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

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

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