Нормальные алгорифмы (алгоритмы).

Нормальные алгорифмы U=<A, > - класс словарных алгоритмов, то есть алгоритмов (применимых к словам некоторого алфавита А), элементарными действиями которых являются подстановки в слова (их кортеж есть схема ).

Всякий нормальный алгоритм, являясь алгоритмом в некотором алфавите А, порождает в нем детерминированный процесс переработки слов. Поэтому любой нормальный алгоритм в фиксированном алфавите А вполне определяется указанием его схемы  - упорядоченного конечного списка формул подстановки в А. Каждая такая формула по существу представляет пару <_Л, _п> слов в А (то есть _Л, _пА^*). Слово _Л называется левой частью этой формулы, а _п – ее правой частью. Среди формул данной схемы некоторые выделяются специально и объявляются заключительными. Обычно в схеме нормального алгоритма заключительная формула записывается в виде _Л _п (, а незаключительная в виде _Л _п. При этом допустимы формулы вида : _Л_п _п; _Л

Нормальный алгоритм U в алфавите А есть предписание строить, исходя из произвольного слова  в А (А^*), последовательность слов _i.

Так, пусть задан алфавит А=1, + и схема подстановок  (здесь  - пустое слово, то есть А^*, Слово  этот алгоритм перерабатывает так:











Процесс оканчивается применением заключительной подстановки, которая перерабатывает слово само в себя. Очевидно, что рассматриваемый алгоритм осуществляет операцию сложения (эквивалентный ему алгоритм <А=1, +, ++, +, >).

Пусть теперь  - некоторое слово в А, то есть А^*. Говорят, что  поддается формуле, если левая часть этой формулы входит просто в . Считается, что всякое слово начинается простым вхождением пустого слова в . Считается, что всякое слово начинается вхождением пустого слова . Поэтому всякое слово поддается формуле с пустой левой частью.

Применением нормального алгоритма U к слову  называется процесс, определяемый следующим правилом (представляющим собой алгоритм выполнения нормального алгоритма):

1. Считать, что i=1. Перейти к пункту 2.

2. Проверить, поддается ли преобразуемое слово i-ой формуле. Если да, то перейти к пункту 3, если нет – к пункту 5.

3. Первое простое вхождение левой части i-ой формулы в преобразуемом слове заменить правой частью i-ой формулы. Результат считать в дальнейшем преобразуемым словом, перейти к пункту 4.

4. Если i-ой формула является заключительной подстановкой, то процесс прекратить. В противном случае перейти к пункту 1.

5. Проверить, имеет ли место равенство i=n. Если да, то процесс прекратить, в противном случае перейти к пункту 6.

6. Увеличить значение i на 1 и перейти к пункту 2.

Любое слово в алфавите А может служить исходными данными для нормального алгоритма в алфавите А. При этом возможны случаи:

1. Процесс выполнения нормального алгоритма для слова А^* заканчивается формулой _Л _п после конечного числа шагов. При этом говорят, что нормальный алгоритм применим к слову , и полученное после его выполнение слово ^* называется результатом.

2. Процесс выполнения нормального алгоритма при исходном слове А^* никогда не заканчивается или происходит безрезультативная остановка (то есть не на формуле _Л _п). В этом случае говорят, что нормальный алгоритм не применим к слову .

Пример:

Алгоритм U=             «обращает» любое слово в А, то есть перерабатывает его в слово, записанное в обратном порядке (его можно записать как 100 с тем, чтобы использовать ).

Так, слово 100 этот нормальный алгоритм последовательно перерабатывает в слова   010, 001, 001, 001, 001, 001, 001, 001, 001, 001, 001, 001, 001.

Замечание:

Последний член этой последовательности считается результатом применения алгоритма U к слову =100 и обозначается символом U(). При этом считается, что U перерабатывает =100 в =001, и пишут U()= (в нашем примере U(100)=001).

Пример:

Алгоритм U=<a, b, <a b; baaba, aa> реализует предписание: «Взяв какое-либо слово a, b^* в качестве исходного, (где а, ba, aa), делай допустимые переходы до тех пор, пока не получится слово вида aa, тогда остановись: слово и есть результат».

Так, взяв слово babaa в качестве исходного данного после первого перехода (то есть применив формулу ba aba ), получим baaaba (здесь =baa), а после второго (то есть применив снова формулу ba aba) имеем aabaaba (здесь =ааba). Применив формулу aa к слову aabaaba получим результат baaba (то есть U(babaa)=baaba).

Однако, взяв в качестве исходного данного слова =baaba, получим бесконечную последовательность abaaba, baabab, abababa, bababab, babababa, … в которой не будет слова aa. Это означает, что алгоритм U не будет применим к слову =baaba.

Если же исходным данным взять слово abaab, то получим конечную последовательность baabb, abbaba, bbabab, в которой к последнему слову нельзя применить допустимый переход, то есть это случай безрезультативной остановки (это означает также неприменимость заданного алгоритма U к слову abaab).

Считается, что для любого алгоритма В в алфавите А может быть построен нормальный алгоритм U над этим алфавитом, перерабатывающий произвольное слово А^* в тот же самый результат, в который перерабатывает его исходный алгоритм В. Это соглашение известно в теории алгоритмов под названием принципа нормализации.

Уточнение понятия алгоритма, осуществленного на основании понятия нормального алгоритма, оказывается эквивалентным другим известным уточнениям (в частности, на основе абстрактной машины Тьюринга). Вследствие этого принцип нормализации оказывается равносильным тезису Черча, предлагающему считать понятие частично рекурсивной функции адекватным уточнением понятия вычислимой арифметической функции f:Nⁿ₀N₀, N₀=N0, nN (к ней путем метода арифметизации могут быть приведены числовые и нечисловые функции).