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 → D {\displaystyle L\to D} , where L {\displaystyle L} and D {\displaystyle D} are two arbitrary strings in the alphabet. Similarly, final substitution formulas are represented by strings of the form L → ⋅ D {\displaystyle L\to \cdot D} . Here is an example of a normal algorithm scheme in the five-letter alphabet | ∗ a b c {\displaystyle |*abc} :
{ | b → b a | a b → b a b → ∗ | → b ∗ ∗ → c | c → c a c → c | c → ⋅ {\displaystyle \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.}
… excerpt ends here. Continue reading the full article.
