|
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 <math>L\to D</math>, where {\displaystyle <math>L}</math> and {\ displaystyle <math>D}</math> – are two arbitrary words in the alphabet of the algorithm (called, respectively, the left and right side of the formula substitution). Similarly, the final substitution formulas are called words of the form {\displaystyle <math>L \to \cdot D}</math>, where {\displaystyle <math>L}</math> and {\displaystyle <math>D}</math> – are two arbitrary words in the alphabet of the algorithm. This assumes that the auxiliary characters {\displaystyle <math>\to}</math> and {\displaystyle <math>\to \cdot}</math> do not belong to the alphabet of the algorithm (otherwise an executable their role divider left and right sides should select the other two letters).
An example of a normal algorithm scheme in five-letter alphabet {\displaystyle <math>| * abc}</math> can serve the following scheme:
<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 word {\displaystyle <math>V}</math> in the alphabet of this algorithm is a discrete sequence of elementary steps, consisting of the following. Let’s assume that {\displaystyle <math>V'}</math> is the word obtained in the previous step of the algorithm (or the original word {\displaystyle <math>V}</math>, if the current step is the first). If among formulas of substitution there is no left-hand side of which would be included in the {\displaystyle <math>V'}</math>, then the work of the algorithm is considered completed, and the result of this work is considered to be the word {\displaystyle <math>V'}</math>. Otherwise, including the substitution of the left side of which is included in the {\displaystyle <math>V'}</math>, the very first part is selected. If the substitution formula looks like {\displaystyle <math>L \to \cdot D}</math>, then out of all of possible representations of the word {\displaystyle <math>V'}</math> that looks like {\displaystyle <math>RLS}</math> it is chosen one {\displaystyle <math>R}</math>, which is the shortest. Then the work of the algorithm is considered completed with the result {\displaystyle <math>RDS}</math>. However, if this substitution formula looks like {\displaystyle <math>L \to D}</math>, then out of all of possible representations of the word {\displaystyle <math>V '}</math> in the form of {\displaystyle <math>RLS}</math> it is chosen one, in which {\displaystyle <math>R}</math> – the shortest, after which the word {\displaystyle <math>RDS}</math> is considered to be the result of the current step, subject to further processing in the next step.
For example, during the process of applying the algorithm to the scheme diagram above the word {\displaystyle <math>| * ||}</math> consistently emerging the words {\displaystyle <math>| b * |}</math>, {\displaystyle <math>ba | * |}</math>, {\displaystyle <math>a | * |}</math>, {\displaystyle <math>a | b *}</math>, {\displaystyle <math>aba | *}</math>, {\displaystyle <math>baa | *}</math>, {\displaystyle <math>aa | *}</math>, {\displaystyle <math>aa | c}</math>, {\displaystyle <math>aac}</math>, {\displaystyle <math>ac |}</math> and {\displaystyleи <math>c ||}</math>, after which the algorithm stops with the result {\displaystyle <math>||}</math>. Other examples, see below.
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."
|
