Markov algorithm

This is an old revision of this page, as edited by 217.37.214.121 (talk) at 12:49, 11 April 2003 (italics, Markov, A.A.). 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 a in power to a Turing machine.

References:

  • Markov, A.A. 1960. The Theory of Algorithms. American Mathematical Society Translations, series 2, 15, 1-14.