A Markov algorithm, names after the Soviet mathematician Andrey Markov, Jr., is a string rewriting system that uses replacement rules to operate on a string of symbols. Markov algorithms have been shown to be Turing complete. They are also known in Russian as Normal Algorithms of Markov (нормальные алгоритмы Маркова or НАМ). Existing implementations of Markov algorithms act as an esoteric language.
At least one high-level programming language, Refal, is based on generalizing Markov algorithms.
The process of applying the normal algorithm to an arbitrary string in the alphabet of this algorithm is a discrete sequence of elementary steps, consisting of the following. Let’s assume that is the word obtained in the previous step of the algorithm (or the original word , if the current step is the first). If of the substitution formulas there is no left-hand side which is included in the , then the algorithm terminates, and the result of its work is considered to be the string . Otherwise, the first of the substitution formulae whose left sides are included in is selected. If the substitution formula is of the form , then out of all of possible representations of the string of the form (where and are arbitrary strings) the one with the shortest is chosen. Then the algorithm terminates and the result of its work is considered to be . However, if this substitution formula is of the form , then out of all of the possible representations of the string of the form of the one with the shortest is chosen, after which the string 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 results in the sequence of words , , , , , , , , , and , after which the algorithm stops with the result .
For other examples, see below.
Any normal algorithm is equivalent to some Turing machine, and vice versa 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."
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.
The following example shows the basic operation of a Markov algorithm.
- "A" -> "apple"
- "B" -> "bag"
- "S" -> "shop"
- "T" -> "the"
- "the shop" -> "my brother"
- "a never used" -> ."terminating rule"
"I bought a B of As from T S."
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.
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.
- "|0" -> "0||"
- "1" -> "0|"
- "0" -> ""
If the algorithm is applied to the above example, it will terminate after the following steps.
- Andrey Andreevich Markov 1960. The Theory of Algorithms. American Mathematical Society Translations, series 2, 15, 1-14.