Markov algorithm
In theoretical computer science, 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. Markov algorithms are named after the mathematician Andrey Markov, Jr.
Refal is a programming language based on Markov algorithms.
Algorithm
The Rules is a sequence of pair of strings, usually presented in the form of pattern → replacement. Some rules may be terminating.
Given an input string:
- Check the Rules in order from top to bottom to see whether any of the patterns can be found in the input string.
- If none is found, the algorithm stops.
- If one (or more) is found, use the first of them to replace the leftmost matching text in the input string with its replacement.
- If the applied rule was a terminating one, the algorithm stops.
- 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 binary numbers to their unary counterparts. For example: 101 will be rewritten to a string of 5 consecutive bars.
Rules
- "|0" -> "0||"
- "1" -> "0|"
- "0" -> ""
Symbol string
"101"
Execution
If the algorithm is applied to the above example, it will terminate after the following steps.
- "0|01"
- "00||1"
- "00||0|"
- "00|0|||"
- "000|||||"
- "00|||||"
- "0|||||"
- "|||||"
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.