Content deleted Content added
mNo edit summary |
|||
| (80 intermediate revisions by 67 users not shown) | |||
Line 1:
{{Short description|Algorithm operating on grammar-like rules}}
A '''Markov algorithm''' is a [[string rewriting system]] that uses [[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.▼
{{No footnotes|date=May 2020}}
▲
[[Refal]] is a [[programming language]] based on '''Markov algorithm'''.▼
==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==
#Check the Rules in order from top to bottom to see whether any of the strings to the left of the arrow can be found in the Symbol string.▼
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.
#If none are found, stop executing the Algorithm.▼
Given an ''input'' string:
#If the applied rule was a terminating one, stop executing the Algorithm.▼
▲#Check the Rules in order from top to bottom to see whether any of the
#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
#Go to step 1.
Note that after each rule application the search starts over from the first rule.
==Example==
Line 27 ⟶ 58:
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."
Line 35 ⟶ 67:
The algorithm will then terminate.
==Another
These rules give a more interesting example. They rewrite binary numbers to their unary counterparts. For example
===Rules===
#"|0" -> "0||"
#"1" -> "0|"
Line 50 ⟶ 83:
If the algorithm is applied to the above example, it will terminate after the following steps.
#"101"
#"0|01"
#"00||1"
Line 58 ⟶ 92:
#"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,
* [[Andrey Markov Jr.|Andrey Andreevich Markov (
<references />
==External links==
* [
* [
* [https://web.archive.org/web/20060217113205/http://nic-nac-project.de/~jcm/index.php?nav=projects Markov algorithm interpreter]
* [
* [https://store.steampowered.com/app/1720850/AB/ A=B, a game about writing substitution rules for a Markov algorithm]
[[Category:Theory of computation]]▼
{{Strings}}
▲[[Category:Theory of computation]]
[[Category:Rewriting systems]]
[[Category:Models of computation]]
| |||