Markov algorithm

2025-09-06T20:35:03Z

2600:1700:4770:C21F:A980:6998:66FB:3448: /* Symbol string */

{{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.|Andrey Markov, Jr.]]

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

==Description==

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: an ''alphabet'', which is a set of symbols, and a ''scheme''. The algorithm is applied to strings of symbols of the alphabet. The scheme is a finite ordered set of ''substitution formulas''. Each formula 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. Similarly, final substitution formulas are represented by strings of the form <math>L\to\cdot D</math>.

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

: <math>\left\{\begin{matrix} |b&\to& ba|\\ ab&\to& ba\\ b&\to&\\ {*}|&\to& b*& \\ {*}&\to& c& \\
|c&\to& c\\ ac&\to& c|\\ c&\to\cdot\end{matrix}\right.</math>

The process of applying the normal algorithm to an arbitrary string <math>V</math> in the alphabet of this algorithm is a discrete sequence of elementary steps, consisting of the following. Let’s assume that <math>V'</math> is the word obtained in the previous step of the algorithm (or the original word <math>V</math>, if the current step is the first). If of the substitution formulas there is no left-hand side which is included in the <math>V'</math>, then the algorithm terminates, and the result of its work is considered to be the string <math>V'</math>. Otherwise, the first of the substitution formulae whose left sides are included in <math>V'</math> is selected. If the substitution formula is of the form <math>L\to\cdot D</math>, then out of all of possible representations of the string <math>V'</math> of the form <math>RLS</math> (where <math>R</math> and <math>S</math> are arbitrary strings) the one with the shortest <math>R</math> is chosen. Then the algorithm terminates and the result of its work is considered to be <math>RDS</math>. However, if this substitution formula is of the form <math>L\to D</math>, then out of all of the possible representations of the string <math>V'</math> of the form of <math>RLS</math> the one with the shortest <math>R</math> is chosen, after which the string <math>RDS</math> is considered to be the result of the current step, subject to further processing in the next step.

For example, the process of applying the algorithm described above to the word <math>|*||</math> results in the sequence of words <math>|b*|</math>, <math>ba|*|</math>, <math>a|*|</math>, <math>a|b*</math>, <math>aba|*</math>, <math>baa|*</math>, <math>aa|*</math>, <math>aa|c</math>, <math>aac</math>, <math>ac|</math> and <math>c||</math>, after which the algorithm stops with the result <math>||</math>.

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–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]].

==Algorithm==

The ''Rules'' are a sequence of pairs of strings, usually presented in the form of ''pattern'' → ''replacement''. Each rule may be either ordinary or terminating.

Given an ''input'' string:

#Check the Rules in order from top to bottom to see whether any of the ''patterns'' can be found in the ''input'' string.
#If none is found, the algorithm stops.
#If one (or more) is found, use '''the first''' of them to replace the leftmost occurrence of matched text in the ''input'' string with its ''replacement''.
#If the rule just applied was a terminating one, the algorithm stops.
#Go to step 1.

Note that after each rule application the search starts over from the first rule.

==Example==
The following example shows the basic operation of a Markov algorithm.

===Rules===
#"A" -> "apple"
#"B" -> "bag"
#"S" -> "shop"
#"T" -> "the"
#"the shop" -> "my brother"
#"a never used" -> '''.'''"terminating rule"

===Symbol string===
"I bought a B of As from T S."

===Execution===
If the algorithm is applied to the above example, the Symbol string will change in the following manner.

#"I bought a B of As from T S."
#"I bought a B of apples from T S."
#"I bought a bag of apples from T S."
#"I bought a bag of apples from T shop."
#"I bought a bag of apples from the shop."
#"I bought a bag of apples from my brother."

The algorithm will then terminate.

==Another example==

These rules give a more interesting example. They rewrite binary numbers to their unary counterparts. For example, 101 will be rewritten to a string of 5 consecutive bars.

===Rules===

#"|0" -> "0||"
#"1" -> "0|"
#"0" -> ""

===Symbol string===
"101"

===Execution===
If the algorithm is applied to the above example, it will terminate after the following steps.

#"101"
#"0|01"
#"00||1"
#"00||0|"
#"00|0|||"
#"000|||||"
#"00|||||"
#"0|||||"
#"|||||"

==See also==
* [[Formal grammar]]

==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 Jr.|Andrey Andreevich Markov (1903–1979)]] 1960. ''The Theory of Algorithms.'' American Mathematical Society Translations, series 2, 15, 1–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 />

==External links==
* [https://yad-studio.github.io/ Yad Studio - Markov algorithms IDE and interpreter (Open Source)]
* [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]
* [https://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]]
[[Category:Rewriting systems]]
[[Category:Models of computation]]

Vero - Wikipedia - User contributions [en]

Markov algorithm