Markov algorithm

This is an old revision of this page, as edited by 80.179.192.157 (talk) at 18:30, 14 May 2003 (Link to Markov chain). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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 be a general model of computation, and can thus be shown to be equivalent to 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.