In theoretical computer science

Theoretical computer science

Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....

, a Markov algorithm is a string rewriting system that uses grammar

Formal grammar

A formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...

-like rules to operate on strings

String (computer science)

In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....

 of symbols. Markov algorithms have been shown to be Turing-complete, which means that they are suitable as a general model of computation

Computation

Computation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...

 and can represent any mathematical expression from its simple notation. Markov algorithms are named after the mathematician Andrey Markov Jr

Andrey Markov (Soviet mathematician)

Andrey Andreyevich Markov Jr. was a Soviet mathematician, the son of the great Russian mathematician Andrey Andreyevich Markov Sr, and one of the key founders of the Russian school of constructive mathematics and logic...

.

Refal

Refal

Refal "is a functional programming language oriented toward symbol manipulation", including "string processing, translation, [and] artificial intelligence". It is one of the oldest members of this family, first conceived in 1966 as a theoretical tool with the first implementation appearing in 1968...

 is a programming language

Programming language

A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....

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:

1. Check the Rules in order from top to bottom to see whether any of the patterns can be found in the input string.
2. If none is found, the algorithm stops.
3. If one (or more) is found, use the first of them to replace the leftmost matching text in the input string with its replacement.
4. If the applied rule was a terminating one, the algorithm stops.
5. Return to step 1 and carry on.

Rules

1. "A" -> "apple"
2. "B" -> "bag"
3. "S" -> "shop"
4. "T" -> "the"
5. "the shop" -> "my brother"
6. "a never used" -> ."terminating rule"

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 apples from T S."
2. "I bought a bag of apples from T S."
3. "I bought a bag of apples from T shop."
4. "I bought a bag of apples from the shop."
5. "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.

Execution

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

1. "0|01"
2. "00||1"
3. "00||0|"
4. "00|0|||"
5. "000|||||"
6. "00|||||"
7. "0|||||"
8. "|||||"

External links

• Online Markov algorithm interpreter
• Markov algorithm interpreter
• Markov algorithm interpreter