Markov algorithm

In theoretical computer science, a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on 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.
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: the definition of the "alphabet" of the algorithm (the algorithm will be applied to strings of these alphabet symbols), and the definition of its "scheme". The scheme of a normal algorithm is a finite ordered set of so-called "substitution formulas", each of which can be "simple" or "final". Simple substitution formulas are represented by strings of the form formula_1, where formula_2 and formula_3 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 formula_4, where formula_2 and formula_3 are two arbitrary strings in the alphabet of the algorithm. This assumes that the auxiliary characters formula_7 and formula_8 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 formula_9:
The process of applying the normal algorithm to an arbitrary string formula_11 in the alphabet of this algorithm is a discrete sequence of elementary steps, consisting of the following. Let’s assume that formula_12 is the word obtained in the previous step of the algorithm (or the original word formula_11, if the current step is the first). If of the substitution formulas there is no left-hand side which is included in the formula_12, then the algorithm terminates, and the result of its work is considered to be the string formula_12. Otherwise, the first of the substitution formulae whose left sides are included in formula_12 is selected. If the substitution formula is of the form formula_4, then out of all of possible representations of the string formula_12 of the form formula_19 (where formula_20 and formula_21 are arbitrary strings) the one with the shortest formula_20 is chosen. Then the algorithm terminates and the result of its work is considered to be formula_23. However, if this substitution formula is of the form formula_1, then out of all of the possible representations of the string formula_12 of the form of formula_19 the one with the shortest formula_20 is chosen, after which the string formula_23 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 formula_29 results in the sequence of words formula_30, formula_31, formula_32, formula_33, formula_34, formula_35, formula_36, formula_37, formula_38, formula_39 and formula_40, after which the algorithm stops with the result formula_41. 
For other examples, see below.
Any normal algorithm is equivalent to some Turing machine, and vice versaany 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 informationfor 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: 
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.
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.
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.
Symbol string.
"101"
Execution.
If the algorithm is applied to the above example, it will terminate after the following steps.