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.
Contents
Refal is a programming language based on Markov algorithms.
Description
Normal algorithms are verbal, that is intended to be applied to words in different alphabets.
Definition of any normal algorithm consists of two parts: the definition of the alphabet algorithm (the algorithm will be applied to words of these alphabet symbols), and the definition of its scheme. Scheme normal algorithm is a finite ordered set of so-called substitution formulas, each of which can be simple or final. A simple formula substitutions are called words such as
An example of a normal algorithm scheme in five-letter alphabet
The process of applying the normal algorithm to an arbitrary word
For example, during the process of applying the algorithm to the scheme diagram above the word
Any normal algorithm is equivalent to some Turing machine, and vice versa – any Turing machine is equivalent to some normal algorithm. A version of the Church-Turing thesis formulated in relation to the normal algorithm is called the "principle of normalization."
Normal algorithms have proved to be a convenient means for the construction of many sections of constructive mathematics. Moreover, inherent in the definition of a normal algorithm used in a number of ideas aimed at handling symbolic information programming languages – for example, in Refal.
Algorithm
The Rules is a sequence of pair 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 string.
- 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 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|||||"
- "|||||"