Markov algorithm (Ofer Abarbanel online library)

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:

  1. Check the Rules in order from top to bottom to see whether any of the patternscan be found in the input
  2. If none is found, the algorithm stops.
  3. 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.
  4. If the rule just applied was a terminating one, the algorithm stops.
  5. 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”

  1. “B” -> “bag”
  2. “S” -> “shop”
  3. “T” -> “the”
  4. “the shop” -> “my brother”
  5. “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 As from T S.”
  2. “I bought a B of apples from T S.”
  3. “I bought a bag of apples from T S.”
  4. “I bought a bag of apples from T shop.”
  5. “I bought a bag of apples from the shop.”
  6. “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. “1” -> “0|”
  2. “0” -> “”

Symbol string

“101”

Execution

If the algorithm is applied to the above example, it will terminate after the following steps.

  1. “101”
  2. “0|01”
  3. “00||1”
  4. “00||0|”
  5. “00|0|||”
  6. “000|||||”
  7. “00|||||”
  8. “0|||||”
  9. “|||||”

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

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library