Editing Markov algorithm (section)

==Description==

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

The definition of any normal algorithm consists of two parts: an ''alphabet'', which is a set of symbols, and a ''scheme''. The algorithm is applied to strings of symbols of the alphabet. The scheme is a finite ordered set of ''substitution formulas''. Each formula can be either ''simple'' or ''final''. Simple substitution formulas are represented by strings of the form <math>L\to D</math>, where <math>L</math> and <math>D</math> are two arbitrary strings in the alphabet. Similarly, final substitution formulas are represented by strings of the form <math>L\to\cdot D</math>.

Here is an example of a normal algorithm scheme in the five-letter alphabet <math>|*abc</math>:

: <math>\left\{\begin{matrix} |b&\to& ba|\\ ab&\to& ba\\ b&\to&\\ {*}|&\to& b*& \\ {*}&\to& c& \\
|c&\to& c\\ ac&\to& c|\\ c&\to\cdot\end{matrix}\right.</math>

The process of applying the normal algorithm to an arbitrary string <math>V</math> in the alphabet of this algorithm is a discrete sequence of elementary steps, consisting of the following. Let’s assume that <math>V'</math> is the word obtained in the previous step of the algorithm (or the original word <math>V</math>, if the current step is the first). If of the substitution formulas there is no left-hand side which is included in the <math>V'</math>, then the algorithm terminates, and the result of its work is considered to be the string <math>V'</math>. Otherwise, the first of the substitution formulae whose left sides are included in <math>V'</math> is selected. If the substitution formula is of the form <math>L\to\cdot D</math>, then out of all of possible representations of the string <math>V'</math> of the form <math>RLS</math> (where <math>R</math> and <math>S</math> are arbitrary strings) the one with the shortest <math>R</math> is chosen. Then the algorithm terminates and the result of its work is considered to be <math>RDS</math>. However, if this substitution formula is of the form <math>L\to D</math>, then out of all of the possible representations of the string <math>V'</math> of the form of <math>RLS</math> the one with the shortest <math>R</math> is chosen, after which the string <math>RDS</math> is considered to be the result of the current step, subject to further processing in the next step.

For example, the process of applying the algorithm described above to the word <math>|*||</math> results in the sequence of words <math>|b*|</math>, <math>ba|*|</math>, <math>a|*|</math>, <math>a|b*</math>, <math>aba|*</math>, <math>baa|*</math>, <math>aa|*</math>, <math>aa|c</math>, <math>aac</math>, <math>ac|</math> and <math>c||</math>, after which the algorithm stops with the result <math>||</math>.    

For other examples, see below.

Any normal algorithm is equivalent to some [[Turing machine]], and vice versa{{snd}}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 are a number of ideas used in programming languages aimed at handling symbolic information{{snd}}for example, in [[Refal]].