# 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 this model is Turing-complete, Markov algorithms can represent any mathematical expression from its simple notation.

 Contents

## 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 are 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.

## 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 marked binary numbers to their unary counterparts. For example: a1101101101b will be rewritten to a string of 877 consecutive ones.

1. "0xb" -> "b0"
2. "1xb" -> "b1"
3. "0x1" -> "10x"
4. "0x0" -> "00x"
5. "1x1" -> "11x"
6. "1x0" -> "01x"
7. "a0" -> "a0x"
8. "a1" -> "a1x"
9. "ab" -> "u"
10. "u1" -> "1ju"
11. "u0" -> "ju"
12. "j1" -> "11j"
13. "j" -> ""
14. "u" -> ""

## 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.

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy