Нормальный Алгорифм

- название, закрепившееся за алгоритмами некоторого точно охарактеризованного типа. Наряду с рекурсивными функциями и Тьюринга машинами Н. А. Получили известность в качестве одного из наиболее удобных уточнений общего интуитивного представления об алгоритме. Понятие Н. А. Было выработано в 1947 А. А. Марковым в ходе его исследований по проблеме тождества для ассоциативных систем (см. Ассоциативное исчисление). Детально определение и общая теория Н. А. Изложены в [1] (гл. I-V). Всякий Н. А. , являясь алгоритмом в нек-ром алфавите А, порождает в нем детерминированный процесс переработки слов. Указание этого алфавита входит в определение Н. А. в качестве обязательной составной части, и в рассматриваемой ситуации про Н. А. Говорят, что он является Н.

А. В алфавите А. Любой Н. А. В фиксированном алфавите Авполне определяется указанием его схемы - упорядоченного конечного списка формул подстановки в А. Каждая такая формула по существу представляет собой упорядоченную пару (U, V )слов в А. Слово Uназ. Левой частью этой формулы, а V- ее правой частью. Среди формул данной схемы нек-рые выделяются специально и объявляются заключительными. Обычно в схеме Н. А. Заключительная формула записывается в виде а незаключительная - в виде Н. А. в алфавите Аесть предписание строить, исходя из произвольного слова Рв А, последовательность слов согласно следующему правилу. Слово Рберется в качестве начального члена этой последовательности, и процесс ее построения продолжается далее.

Пусть для нек-рого слово построено и процесс построения рассматриваемой последовательности еще не завершился. Если в схеме Н. А.нет формул, левые части к-рых входили бы в полагают равным и процесс построения последовательности на этом считается закончившимся. Если же в схеме имеются формулы с левыми частями, входящими в то в качестве берется результат подстановки правой части первой из таких формул вместо первого вхождения ее левой части в слово при этом процесс построения последовательности считается завершившимся, если примененная на этом шаге формула подстановки была заключительной, и продолжающимся в противном случае. Если процесс построения упомянутой последовательности обрывается, то говорят, что рассматриваемый Н.

А. Применим к слову Р. Последний член этой последовательности считается результатом применения Н. А. К слову Ри обозначается символом . При этом говорят, что перерабатывает Р в Q, и пишут . Н. А. В каком-либо расширении алфавита Аназ. Н. А. Над этим алфавитом. Имеются веские основания считать, что уточнение общего представления об алгоритме в алфавите, произведенное с помощью понятия Н. А., является адекватным. Именно, считается, что для всякого алгоритма в каком-либо алфавите Аможет быть построен Н. А. Над этим алфавитом, перерабатывающий произвольное слово Рв Ав тот же самый результат, в к-рый перерабатывает его исходный алгоритм . Это соглашение известно в теории алгоритмов под названием принципа нормализации. Уточнение понятия алгоритма, осуществленное на основе понятия Н.

А., оказывается эквивалентным другим известным уточнениям (см., напр., [2]). Вследствие этого принцип нормализации оказывается равносильным Чёрча тезису, предлагающему считать понятие частично рекурсивной функции адекватным уточнением понятия вычислимой арифметич. Функции. Возникшие первоначально в связи с алгебраич. Проблематикой Н. А. Оказались удобным рабочим аппаратом во многих исследованиях, требующих точного понятия алгоритма,- особенно тогда, когда основные объекты рассмотрения имеют неарифметич. Природу и допускают удобное представление в виде слов в нек-рых алфавитах (такова, напр., ситуация в конструктивном анализе). Лит.:[1] Марков А. А., Теория алгорифмов, М., 1954 (Тр. Матем. Ин-та АН СССР, т. 42). [2] Мендельсон Э., Введение в математическую логику, пер.

С англ., М., 1971. Н. М. Нагорный..