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
- 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.
- If none are found, stop executing the Algorithm.
- 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.
- If the applied rule was a terminating one, stop executing the Algorithm.
- Return to step 1 and carry on.
Example
The following example shows the basic operation of a Markov algorithm.
Rules
- "A" -> "apple"
- "B" -> "bag"
- "S" -> "shop"
- "T" -> "the"
- "the shop" -> "my brother"
- "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.
- "I bought a B of apples from T S."
- "I bought a bag of apples from T S."
- "I bought a bag of apples from T shop."
- "I bought a bag of apples from the shop."
- "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.
- "0xb" -> "b0"
- "1xb" -> "b1"
- "0x1" -> "10x"
- "0x0" -> "00x"
- "1x1" -> "11x"
- "1x0" -> "01x"
- "a0" -> "a0x"
- "a1" -> "a1x"
- "ab" -> "u"
- "u1" -> "1ju"
- "u0" -> "ju"
- "j1" -> "11j"
- "j" -> ""
- "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.
External link
- Markow algorithm interpreter (http://nic-nac-project.de/~jcm/index.php?nav=projects)