Encyclopedia > Markov algorithm

  Article Content

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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
U.S. presidential election, 1804

...     Contents U.S. presidential election, 1804 Presidential CandidateElectoral Vote Party Running Mate(Electoral Votes) Thomas Jefferson ...

 
 
 
This page was created in 33.4 ms