Markov algorithm
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 have sufficient power to be a general model of
computation, and can thus be shown to be equivalent in power to a
Turing machine. Since it is
Turing-complete, Markov chains can represent any
mathematical expression from its simple notation.
References:
- Caracciolo di Forino, A. String processing languages and generalized Markov algorithms. In Symbol manipulation languages and techniques, D. G. Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, The Netherlands, 1968, pp. 191-206.
- Markov, A.A 1960. The Theory of Algorithms. American Mathematical Society Translations, series 2, 15, 1-14.
External link