Content deleted Content added
rm 1-sentence copyright violation |
mNo edit summary |
||
(138 intermediate revisions by more than 100 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.|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]]
|