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.
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\toD
L
D
L\to ⋅ 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 ⋅ \end{matrix}\right.
The process of applying the normal algorithm to an arbitrary string
V
V'
V
V'
V'
V'
L\to ⋅ D
V'
RLS
R
S
R
RDS
L\toD
V'
RLS
R
RDS
For example, the process of applying the algorithm described above to the word
|*||
|b*|
ba|*|
a|*|
a|b*
aba|*
baa|*
aa|*
aa|c
aac
ac|
c||
||
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.
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.
The following example shows the basic operation of a Markov algorithm.
"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.
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.
"101"
If the algorithm is applied to the above example, it will terminate after the following steps.