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

- название, закрепившееся за алгоритмами некоторого точно охарактеризованного типа. Наряду с рекурсивными функциями и Тьюринга машинами Н. а. получили известность в качестве одного из наиболее удобных уточнений общего интуитивного представления об алгоритме. Понятие Н. а. было выработано в 1947 А. А. Марковым в ходе его исследований по проблеме тождества для ассоциативных систем (см. Ассоциативное исчисление). Детально определение и общая теория Н. а. изложены в [1] (гл. I-V). Всякий Н. а. [img: http://localhost:8080/file/031512-164.jpg], являясь алгоритмом в нек-ром алфавите А, порождает в нем детерминированный процесс переработки слов. Указание этого алфавита входит в определение Н. а. [img: http://localhost:8080/file/031512-165.jpg] в качестве обязательной составной части, и в рассматриваемой ситуации про Н. а. [img: http://localhost:8080/file/031512-166.jpg] говорят, что он является Н. а. в алфавите А. Любой Н. а. в фиксированном алфавите Авполне определяется указанием его схемы - упорядоченного конечного списка формул подстановки в А. Каждая такая формула по существу представляет собой упорядоченную пару (U, V)слов в А. Слово Uназ. левой частью этой формулы, а V- ее правой частью. Среди формул данной схемы нек-рые выделяются специально и объявляются заключительными. Обычно в схеме Н. а. заключительная формула записывается в виде [img: http://localhost:8080/file/031512-167.jpg] а незаключительная - в виде [img: http://localhost:8080/file/031512-168.jpg] Н. а. [img: http://localhost:8080/file/031512-169.jpg] в алфавите Аесть предписание строить, исходя из произвольного слова Рв А, последовательность слов [img: http://localhost:8080/file/031512-170.jpg] согласно следующему правилу. Слово Рберется в качестве начального члена [img: http://localhost:8080/file/031512-171.jpg] этой последовательности, и процесс ее построения продолжается далее. Пусть для нек-рого [img: http://localhost:8080/file/031512-172.jpg] слово [img: http://localhost:8080/file/031512-173.jpg] построено и процесс построения рассматриваемой последовательности еще не завершился. Если в схеме Н. а. [img: http://localhost:8080/file/031512-174.jpg] нет формул, левые части к-рых входили бы в [img: http://localhost:8080/file/031512-175.jpg] полагают равным [img: http://localhost:8080/file/031512-176.jpg] и процесс построения последовательности на этом считается закончившимся. Если же в схеме [img: http://localhost:8080/file/031512-177.jpg] имеются формулы с левыми частями, входящими в [img: http://localhost:8080/file/031512-178.jpg] то в качестве [img: http://localhost:8080/file/031512-179.jpg] берется результат подстановки правой части первой из таких формул вместо первого вхождения ее левой части в слово [img: http://localhost:8080/file/031512-180.jpg] при этом процесс построения последовательности считается завершившимся, если примененная на этом шаге формула подстановки была заключительной, и продолжающимся в противном случае. Если процесс построения упомянутой последовательности обрывается, то говорят, что рассматриваемый Н. а. [img: http://localhost:8080/file/031512-181.jpg] применим к слову Р. Последний член [img: http://localhost:8080/file/031512-182.jpg] этой последовательности считается результатом применения Н. а. [img: http://localhost:8080/file/031512-183.jpg] к слову Ри обозначается символом [img: http://localhost:8080/file/031512-184.jpg]. При этом говорят, что [img: http://localhost:8080/file/031512-185.jpg] перерабатывает Р в Q, и пишут [img: http://localhost:8080/file/031512-186.jpg]. Н. а. в каком-либо расширении алфавита Аназ. Н. а. над этим алфавитом. Имеются веские основания считать, что уточнение общего представления об алгоритме в алфавите, произведенное с помощью понятия Н. а., является адекватным. Именно, считается, что для всякого алгоритма [img: http://localhost:8080/file/031512-187.jpg] в каком-либо алфавите Аможет быть построен Н. а. [img: http://localhost:8080/file/031512-188.jpg] над этим алфавитом, перерабатывающий произвольное слово Рв Ав тот же самый результат, в к-рый перерабатывает его исходный алгоритм [img: http://localhost:8080/file/031512-189.jpg]. Это соглашение известно в теории алгоритмов под названием принципа нормализации. Уточнение понятия алгоритма, осуществленное на основе понятия Н. а., оказывается эквивалентным другим известным уточнениям (см., напр., [2]). Вследствие этого принцип нормализации оказывается равносильным Чёрча тезису, предлагающему считать понятие частично рекурсивной функции адекватным уточнением понятия вычислимой арифметич. функции. Возникшие первоначально в связи с алгебраич. проблематикой Н. а. оказались удобным рабочим аппаратом во многих исследованиях, требующих точного понятия алгоритма,- особенно тогда, когда основные объекты рассмотрения имеют неарифметич. природу и допускают удобное представление в виде слов в нек-рых алфавитах (такова, напр., ситуация в конструктивном анализе).