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.

L and |∗abc:

V′ is the word obtained in the previous step of the algorithm (or the original word V′. Otherwise, the first of the substitution formulae whose left sides are included in V′ of the form S are arbitrary strings) the one with the shortest L→D, then out of all of the possible representations of the string R is chosen, after which the string |b∗|, a|b∗, aa|∗, ac| and  –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