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.

Normal algorithms are verbal, that is intended to be applied to words in different alphabets.

Definition of any normal algorithm consists of two parts: the definition of the alphabet algorithm (the algorithm will be applied to words of these alphabet symbols), and the definition of its scheme. Scheme normal algorithm is a finite ordered set of so-called substitution formulas, each of which can be simple or final. A simple formula substitutions are called words such as ${\displaystyle L\to D}$, where ${\displaystyle L}$ and ${\displaystyle D}$ – are two arbitrary words in the alphabet of the algorithm (called, respectively, the left and right side of the formula substitution). Similarly, the final substitution formulas are called words of the form ${\displaystyle L\to \cdot D}$, where ${\displaystyle L}$ and ${\displaystyle D}$ – are two arbitrary words in the alphabet of the algorithm. This assumes that the auxiliary characters ${\displaystyle \to }$ and ${\displaystyle \to \cdot }$ do not belong to the alphabet of the algorithm (otherwise an executable their role divider left and right sides should select the other two letters).

...
Wikipedia