Определение слова «Нормальный Алгорифм»

Большая советская энциклопедия:

Нормальный алгорифм
Одно из современных уточнений понятия Алгоритма, получившее распространение в исследованиях по конструктивной математике (См. Конструктивная математика). Предложено в 1950 А. А. Марковым, впервые систематически и строго построившим на основе этого уточнения общую алгоритмов теорию (См. Алгоритмов теория). Н. а. эквивалентны частично-рекурсивным функциям (см. Рекурсивные функции), а следовательно, и Тьюринга машинам.
Концепция Н. а. специально приспособлена для реализации алгоритмов, действующих над словами в тех или иных алфавитах. При этом под алфавитом в математике понимается любой конечный набор четко отличимых друг от друга графических символов (букв), а под словом в данном алфавите — произвольная конечная цепочка букв этого алфавита. Цепочка, вовсе не содержащая букв, также считается словом в данном алфавите (пустое слово). Например, цепочки «ииаам», «книга», «гамма» являются словами в русском алфавите, а также в шестибуквенном алфавите {к, н, и, г, а, м}. Элементарным актом преобразования слов в алгоритмических процессах, задаваемых Н. а., является т. н. операция «подстановки вместо первого вхождения». Пусть Р, Q, R — слова в некотором алфавите. Результатом подстановки Q вместо первого вхождения Р в R называется слово (R, Р, Q), получаемое следующим образом. Если Р входит в R, т.е. R представимо в виде S1PS2, то среди таких представлений отыскивается представление с наиболее коротким словом S1 и полагается (R, Р, Q) = S1QS2. Если же Р не входит в R, то (R, Р, Q) = R. Так, (гамма, а, е) = гемма.
Для задания Н. а. необходимо фиксировать некоторый алфавит А, не содержащий букв «» и « · », и упорядоченный список слов вида Р Q (простая формула подстановки) или Р · Q (заключит. формула подстановки), где Р и Q — слова в А. Формулы подстановок принято записывать друг под другом в порядке следования, объединяя их слева фигурной скобкой. Получающаяся фигура называется схемой Н. а. Исходными данными и результатами работы Н. а. являются слова в А (сам Н. а. называется Н. а. в алфавите А). Процесс применения к слову R Н. а. со схемой вида

где i (1 i n) означает «» или « ·», разворачивается следующим образом. Отыскивается наименьшее i, при котором Pi входит в R. Если все Pi не входят в R, то работа заканчивается и её результатом считается R. Если требуемое i найдено, то переходят к слову (R, Pi, Qi). При этом в случае, если использованная формула подстановки PiiQi была заключительной (i = ), работа заканчивается и результатом считается (R, Pi, Qi). Если же формула PiiQi — простая, то описанная процедура повторяется с заменой R на (R, Ri, Qi).
Пример. Натуральные числа можно рассматривать как слова в алфавите {0, 1} вида 0, 01, 011, .... Н. а. в этом алфавите со схемами {0 · 01 и {1 переводят каждое натуральное число n соответственно в n + 1 и в 0.
Множество всех Н. а. замкнуто относительно известных способов комбинирования алгоритмов. Например, по любым двум Н. а. и можно построить Н. а. , являющийся композицией и , т. е. реализующий следующий интуитивный алгоритм: «сначала выполнить алгоритм , затем к результату применять ».
Соотношение между интуитивными алгоритмами и Н. а. описывается выдвинутым А. А. Марковым принципом нормализации: всякий алгоритм, перерабатывающий слова в данном алфавите А в слова в этом же алфавите, может быть реализован посредством Н. а. в некотором расширении А. [Легко указать очень простые алгоритмы в А, не реализуемые Н. а. в A; с другой стороны, всегда можно ограничиться двухбуквенным (и даже однобуквенным) расширением A.] Принцип нормализации эквивалентен тезису Чёрча и, аналогично последнему, не может быть доказан из-за неточности интуитивной концепции алгоритма.
Лит.: Марков А. А., Теория алгорифмов, М. — Л., 1954 (Тр. Математического института АН СССР, т. 42); Мендельсон Э., Введение в математическую логику, пер. с англ., М., 1971.
Б. А. Кушнер.

Математическая энциклопедия:

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

Смотреть другие определения →