# 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: 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 $L\to D$, where $L$ and $D$ are two arbitrary strings in the alphabet. Similarly, final substitution formulas are represented by strings of the form $L\to \cdot D$.
Here is an example of a normal algorithm scheme in the five-letter alphabet $|*abc$:
    $\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.$
The process of applying the normal algorithm to an arbitrary string $V$ in the alphabet of this algorithm is a discrete sequence of elementary steps, consisting of the following. Let’s assume that $V'$ is the word obtained in the previous step of the algorithm (or the original word $V$, if the current step is the first). If of the substitution formulas there is no left-hand side which is included in the $V'$, then the algorithm terminates, and the result of its work is considered to be the string $V'$. Otherwise, the first of the substitution formulae whose left sides are included in $V'$ is selected. If the substitution formula is of the form $L\to \cdot D$, then out of all of possible representations of the string $V'$ of the form $RLS$ (where $R$ and $S$ are arbitrary strings) the one with the shortest $R$ is chosen. Then the algorithm terminates and the result of its work is considered to be $RDS$. However, if this substitution formula is of the form $L\to D$, then out of all of the possible representations of the string $V'$ of the form of $RLS$ the one with the shortest $R$ is chosen, after which the string $RDS$ 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 $|b*|$, $ba|*|$, $a|*|$, $a|b*$, $aba|*$, $baa|*$, $aa|*$, $aa|c$, $aac$, $ac|$ and $c||$, 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."
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 – 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|||||"