Нормальный алгорифм
Норма́льный алгори́фм, название, закрепившееся за алгоритмами некоторого точно охарактеризованного типа. Наряду с рекурсивными функциями и машинами Тьюринга, нормальные алгорифмы являются одним из наиболее удобных уточнений общего интуитивного представления об алгоритме. Понятие нормального алгорифма было предложено в 1947 г. А. А. Марковым в ходе его исследований по проблеме тождества для ассоциативных систем (проблема Туэ).
Всякий нормальный алгорифм , являясь алгоритмом в некотором алфавите , порождает в нём детерминированный процесс переработки слов. Указание этого алфавита входит в определение нормального алгорифма в качестве составной части, и про нормальный алгорифм говорят, что он является нормальным алгорифмом в алфавите . Любой нормальный алгорифм в фиксированном алфавите вполне определяется указанием его схемы – упорядоченного конечного списка формул подстановки в . Каждая такая формула представляет собой упорядоченную пару слов в . Слово называется левой частью этой формулы, а – её правой частью. Среди вхождений формул в данную схему некоторые выделяются специально и объявляются заключительными. Обычно в схеме нормального алгорифма заключительная формула записывается в виде , а незаключительная – в виде .
Нормальный алгорифм в алфавите есть предписание строить, исходя из произвольного слова в , последовательность слов согласно следующему правилу. Слово берётся в качестве начального слова этой последовательности, и процесс её построения продолжается далее. Пусть для некоторого слово построено и процесс построения рассматриваемой последовательности ещё не завершился. Если в схеме нормального алгорифма нет формул, левые части которых входили бы в , то полагают равным , и процесс построения последовательности на этом считается закончившимся. Если же в схеме имеются формулы с левыми частями, входящими в , то в качестве берётся результат подстановки правой части первой из таких формул вместо первого вхождения её левой части в слово , при этом процесс построения последовательности считается завершившимся, если применённая на этом шаге формула подстановки была заключительной, и продолжается в противном случае. Если процесс построения упомянутой последовательности обрывается, то говорят, что рассматриваемый нормальный алгорифм применим к слову . Последний член этой последовательности считается результатом применения нормального алгорифма к слову и обозначается символом . При этом говорят, что перерабатывает в , и пишут . Нормальный алгорифм в каком-либо расширении алфавита называется нормальным алгорифмом над этим алфавитом.
Имеются основания считать, что уточнение общего представления об алгоритме в алфавите, произведённое с помощью понятия нормального алгорифма, является адекватным. Именно, считается, что для всякого алгоритма в каком-либо алфавите может быть построен нормальный алгорифм над этим алфавитом, перерабатывающий произвольное слово в в тот же самый результат, в который перерабатывает его исходный алгоритм . Это соглашение известно в теории алгоритмов под названием принципа нормализации. Уточнение понятия алгоритма, осуществлённое на основе понятия нормального алгорифма, оказывается эквивалентным другим известным уточнениям. Вследствие этого принцип нормализации равносилен тезису Чёрча, предлагающему считать понятие частично рекурсивной функции адекватным уточнением понятия вычислимой арифметической функции.
Возникшие первоначально в связи с алгебраической проблематикой нормальные алгорифмы оказались удобным рабочим аппаратом во многих исследованиях, требующих точного понятия алгоритма, – особенно тогда, когда основные объекты рассмотрения допускают удобное представление в виде слов в некоторых алфавитах (такова, например, ситуация в конструктивной математике).