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 Soviet mathematician Andrey Markov, Jr.
Refal is a programming language based on Markov algorithms.
The Rules are a sequence of pairs of strings, usually presented in the form of pattern → replacement. Each rule may be either ordinary or terminating.
Given an input string:
- Check the Rules in order from top to bottom to see whether any of the patternscan be found in the input
- If none is found, the algorithm stops.
- If one (or more) is found, use the firstof them to replace the leftmost occurrence of matched text in the input string with its replacement.
- If the rule just applied was a terminating one, the algorithm stops.
- Go to step 1.
Note that after each rule application the search starts over from the first rule.
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”
“I bought a B of As from T S.”
If the algorithm is applied to the above example, the Symbol string will change in the following manner.
- “I bought a B of As from T S.”
- “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.
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” -> “”
If the algorithm is applied to the above example, it will terminate after the following steps.
- 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.