Markov algorithm: Difference between revisions

Revision as of 10:41, 10 October 2020

Latest revision as of 16:10, 14 August 2025

(20 intermediate revisions by 17 users not shown)

Line 1:

{{Short description|Algorithm operating on grammar-like rules}}

{{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.]]<ref|Andrey nameMarkov, = "NKS note a">''[[A New Kind of ScienceJr.]]'' [https://wolframscience.com/nks/notes-3-6--history-of-sequential-substitution-systems/]</ref>

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

Line 9 ⟶ 10:

Normal algorithms are verbal, that is, intended to be applied to strings in different alphabets.

The definition of any normal algorithm consists of two parts: the definition of thean ''alphabet'', which is a set of thesymbols, algorithmand (thea algorithm''scheme''. willThe bealgorithm is applied to strings of these alphabet symbols), andof the definition of its ''scheme''alphabet. The scheme of a normal algorithm is a finite ordered set of so-called ''substitution formulas'',. eachEach of whichformula can be either ''simple'' or ''final''. Simple substitution formulas are represented by strings of the form <math>L\to D</math>, where <math>L</math> and <math>D</math> are two arbitrary strings in the alphabet of the algorithm (called, respectively, the left and right sides of the formula substitution). Similarly, final substitution formulas are represented by strings of the form <math>L\to\cdot D</math>, where <math>L</math> and <math>D</math> are two arbitrary strings in the alphabet of the algorithm. This assumes that the auxiliary characters <math>\to</math> and <math>\to\cdot</math> do not belong to the alphabet of the algorithm (otherwise two other characters to perform their role as the dividers of the left and right sides, which are not in the algorithm's alphabet, should be selected).

Here is an example of a normal algorithm scheme in the five-letter alphabet <math>|*abc</math>:

Line 22 ⟶ 23:

For other examples, see below.

Any normal algorithm is equivalent to some [[Turing machine]], and vice versa{{snd}}any [[Turing machine]] is equivalent to some normal algorithm. A version of the [[Church-TuringChurch–Turing thesis]] formulated in relation to the normal algorithm is called the "principle of normalization."

Normal algorithms have proved to be a convenient means for the construction of many sections of [[constructive mathematics]]. Moreover, inherent in the definition of a normal algorithm are a number of ideas used in programming languages aimed at handling symbolic information{{snd}}for example, in [[Refal]].

Line 93 ⟶ 94:

==See also==

* [[formalFormal grammar]]

* [[Thue (programming language)]]

* [[formal grammar]]

== Notes ==

{{reflist|30em}}

==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, Thethe Netherlands, 1968, pp.&nbsp;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, 11–14. (Translation from the Russian, Trudy Instituta im. Steklova 38 (1951) 176-14189<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 />

==External links==

* [https://yad-studio.github.io/ Yad Studio - Markov algorithms IDE and interpreter (Open Source)]

* [httphttps://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]

{{Strings}}

[[Category:Theory of computation]]