You get a bonus - 1 coin for daily activity. Now you have 1 coin

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

Lecture



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.

Content

  • 1Description
  • 2Examples
    • 2.1 Example 1
    • 2.2 Example 2
  • 3SM. also
    • 3.1Other abstract performers and formal computing systems
    • 3.2 Languages ​​based on normal algorithms
  • 4Links
  • 5Notes

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.   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) where   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) and   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) - 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   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) where   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) and   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) - two arbitrary words in the alphabet of the algorithm. It is assumed that the auxiliary letters   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) and   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) 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   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) can serve as a circuit

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

The process of applying a normal algorithm to an arbitrary word   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) in the alphabet of this algorithm is a discrete sequence of elementary steps, consisting of the following. Let be   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) - the word obtained at the previous step of the algorithm (or the original word   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) 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 normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) , the work of the algorithm is considered complete, and the result of this work is the word   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) . Otherwise, among the substitution formulas, the left part of which is included in   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) , the very first is chosen. If this substitution formula is   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) then of all the possible representations of the word   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) as   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) is chosen such that   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) - the shortest, after which the work of the algorithm is considered complete with the result   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) . If this substitution formula is   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) then of all the possible representations of the word   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) as   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) is chosen such that   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) - the shortest, followed by the word   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) 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   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) words appear consistently   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) ,   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) ,   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) ,   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) ,   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) ,   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) ,   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) ,   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) ,   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) ,   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) and   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) after which the algorithm terminates with the result   The normal algorithm is the Markov algorithm (HAM, also a Markov algorithm) . 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. |||||

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

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

Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Theory of Automata

Terms: Theory of Automata