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. Andrey (Andrei) Andreyevich Markov (Russian: ) (June 14, 1856 N.S. – July 20, 1922) was a Russian mathematician. ... A string rewriting system is a substitution system used to perform computation using Markov algorithms or create certain types of fractals such as the Cantor set or Menger sponge. ... For the rules of English grammar, see English grammar and Disputes in English grammar. ... In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ... In computability theory a programming language or any other logical system is called Turing-complete if it has a computational power equivalent to a universal Turing machine. ... Look up computation in Wiktionary, the free dictionary. ... A mathematical expression is a string of symbols which describes (or expresses) a (potential or actual) computation using operators and operands. ...

Refal is a programming language based on Markov algorithm. A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ...

Algorithm

1. Check the Rules in order from top to bottom to see whether any of the strings to the left of the arrow can be found in the Symbol string.
2. If none is found, stop executing the Algorithm.
3. If one or more is found, replace the leftmost matching text in the Symbol string with the text to the right of the arrow in the first corresponding Rule.
4. If the applied rule was a terminating one, stop executing the Algorithm.
5. Return to step 1 and carry on.

Example

The following example shows the basic operation of a Markov algorithm.

Rules

1. "A" -> "apple"
2. "B" -> "bag"
3. "S" -> "shop"
4. "T" -> "the"
5. "the shop" -> "my brother"
6. "a never used" -> ."terminating rule"

Symbol string

"I bought a B of As from T S."

Execution

If the algorithm is applied to the above example, the Symbol string will change in the following manner.

1. "I bought a B of apples from T S."
2. "I bought a bag of apples from T S."
3. "I bought a bag of apples from T shop."
4. "I bought a bag of apples from the shop."
5. "I bought a bag of apples from my brother."

The algorithm will then terminate.

Another Example

These rules give a more interesting example. They rewrite binary numbers to their unary counterparts. For example: 101 will be rewritten to a string of 5 consecutive bars.

Rules

1. "|0" -> "0||"
2. "1" -> "0|"
3. "0" -> ""

Symbol string

"101"

Execution

If the algorithm is applied to the above example, it will terminate after the following steps.

1. "0|01"
2. "00||1"
3. "00||0|"
4. "00|0|||"
5. "000|||||"
6. "00|||||"
7. "0|||||"
8. "|||||"

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.
• Andrey Andreevich Markov (1903-1979) 1960. The Theory of Algorithms. American Mathematical Society Translations, series 2, 15, 1-14.

External links

• Online Markov algorithm interpreter
• Markov algorithm interpreter
• Markov algorithm interpreter
• Markov algorithm interpreter (Applet)