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.^{[1]}

Refal is a programming language based on Markov algorithms.

Algorithm

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
*patterns*can be found in the*input* - If none is found, the algorithm stops.
- If one (or more) is found, use
**the first**of 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.

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

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.

- “101”
- “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.

Ofer Abarbanel – Executive Profile