Markov algorithm: Difference between revisions

Revision as of 22:13, 9 August 2025

Latest revision as of 16:10, 14 August 2025

Line 2:

{{No footnotes|date=May 2020}}

In [[theoretical computer science]], a '''Markov algorithm''' is a [[string rewriting system]] that uses [[Formal grammar|grammar]]-like rules to operate on [[string (computer science)|strings]] of symbols. Markov algorithms have been shown to be [[Turing-complete]], which means that they are suitable as a general model of [[computation]] and can represent any [[mathematical expression]] from its simple notation. Markov algorithms are named after the Soviet mathematician [[Andrey Markov Jr.|Andrey Markov, Jr.]]

[[Refal]] is a [[programming language]] based on Markov algorithms.

Line 98:

==References==

* Caracciolo di Forino, A. ''String processing languages and generalized Markov algorithms.'' In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, the Netherlands, 1968, pp. 191–206.

* [[Andrey Markov (Soviet mathematician)Jr.|Andrey Andreevich Markov (1903-19791903–1979)]] 1960. ''The Theory of Algorithms.'' American Mathematical Society Translations, series 2, 15, 1-141–14. (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951) 176-189<ref>{{Cite journal |last=Kushner |first=Boris A. |date=1999-05-28 |title=Markov's constructive analysis; a participant's view |url=https://core.ac.uk/works/41825477 |journal=Theoretical Computer Science |language=en |volume=219 |issue=1–2 |pages=268, 284 |doi=10.1016/S0304-3975(98)00291-6|doi-access=free }}</ref>)

<references />

Line 105:

* [https://sourceforge.net/projects/markov Markov algorithm interpreter]

* [https://web.archive.org/web/20060217113205/http://nic-nac-project.de/~jcm/index.php?nav=projects Markov algorithm interpreter]

* [httphttps://rosettacode.org/wiki/Execute_a_Markov_algorithm Markov algorithm interpreters at Rosetta-Code]

* [https://store.steampowered.com/app/1720850/AB/ A=B, a game about writing substitution rules for a Markov algorithm]