The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm)

The normal algorithm (algorithm) of Markov ( HAM , also a Markov algorithm ) is one of the standard ways of formally defining the concept of an algorithm (another well-known method is the Turing machine). The concept of a normal algorithm was introduced by A. A. Markov (the youngest) in the late 1940s in the work on the insolubility of some problems in the theory of associative computing. The traditional spelling and pronunciation of the word “algorithm” in this term also goes back to its author, who has taught many years of mathematical logic at the Faculty of Mechanics and Mathematics of Moscow State University.

The normal algorithm describes a method of rewriting strings, similar in the way of setting formal grammars. NAM is a Turing-complete language, which makes it expressively equivalent to a Turing machine and, therefore, to modern programming languages. On the basis of NAM was created functional programming language Refal.

Description

Normal algorithms are verbal, that is, intended to be applied to words in different alphabets.

The definition of any normal algorithm consists of two parts: the definition of the alphabet of the algorithm (to the words of whose characters the algorithm will be applied) and the definition of its scheme . A scheme of a normal algorithm is called a finite ordered set of so-called substitution formulas , each of which can be simple or final . Simple substitution formulas are words of the form. where and - two arbitrary words in the alphabet of the algorithm (called, respectively, the left and right sides of the substitution formula). Similarly, the final substitution formulas are called words where and - two arbitrary words in the alphabet of the algorithm. It is assumed that the auxiliary letters and do not belong to the alphabet of the algorithm (otherwise, the other two letters should be chosen for the role played by the separator of the left and right sides).

An example of the scheme of the normal algorithm in the five-letter alphabet can serve as a circuit

The process of applying a normal algorithm to an arbitrary word in the alphabet of this algorithm is a discrete sequence of elementary steps, consisting of the following. Let be - the word obtained at the previous step of the algorithm (or the original word if the current step is first). If among the substitution formulas there is no such, the left part of which would be included in , the work of the algorithm is considered complete, and the result of this work is the word . Otherwise, among the substitution formulas, the left part of which is included in , the very first is chosen. If this substitution formula is then of all the possible representations of the word as is chosen such that - the shortest, after which the work of the algorithm is considered complete with the result . If this substitution formula is then of all the possible representations of the word as is chosen such that - the shortest, followed by the word considered to be the result of the current step to be further processed in the next step.

For example, during the process of applying the algorithm with the above scheme to the word words appear consistently , , , , , , , , , and after which the algorithm terminates with the result . See other examples below.

Any normal algorithm is equivalent to some Turing machine, and vice versa - any Turing machine is equivalent to some normal algorithm. A variant of the Church-Turing thesis, formulated in relation to normal algorithms, is usually called the “normalization principle”.

Normal algorithms have proven to be a convenient means for building many sections of constructive mathematics. In addition, the ideas embedded in the definition of a normal algorithm are used in a number of programming languages ​​oriented towards the processing of symbolic information — for example, in Refal.

Examples

Example 1

Using the Markov algorithm for conversions above strings.

Alphabet:

{a ... i, a ... i, "space", "dot"}

Rules:

1. A → Orange
2. kg → kilogram
3. M → shop
4. T → tom
5. shop → stall (final formula)
6. in that stall → in that market

Source line:

I bought kg Aow in T M.

When the algorithm is executed, the line undergoes the following changes:

1. I bought a kg of oranges in T M.
2. I bought a kilo of oranges in T M.
3. I bought a kilo of oranges in a T shop.
4. I bought a kilo of oranges in that shop.
5. I bought a kilo of oranges in that stall.

This completes the algorithm execution (since formula No. 5, which we made final, will be achieved).

Example 2

This algorithm converts binary numbers to "single" (in which the record of a non-negative integer number N is a string of N sticks). For example, the binary number 101 is converted to 5 sticks: |||||.

Alphabet:

{0, 1, | }

Rules:

1. 1 → 0 |
2. | 0 → 0 ||
3. 0 → "" (empty string)

Source line:

101

Performance:

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

see also

Other abstract artists and formal computing systems

• Turing Machine (Automated Programming)
• Machine Post (automatic programming)
• Recursive function (computability theory)
• Lambda calculus (functional programming)
• Brainfuck (imperative programming)

Languages ​​based on normal algorithms

• REFAL
• Thue