алгорифм , одно из современных уточнений понятия алгоритма , получившее распространение в исследованиях по конструктивной математике . Предложено в 1950 А. А. Марковым , впервые систематически и строго построившим на основе этого уточнения общую алгоритмов теорию . Н. а. эквивалентны частично-рекурсивным функциям (см. Рекурсивные функции ), а следовательно, и Тьюринга машинам .
Концепция Н. а. специально приспособлена для реализации алгоритмов, действующих над словами в тех или иных алфавитах. При этом под алфавитом в математике понимается любой конечный набор четко отличимых друг от друга графических символов (букв), а под словом в данном алфавите - произвольная конечная цепочка букв этого алфавита. Цепочка, вовсе не содержащая букв, также считается словом в данном алфавите (пустое слово). Например, цепочки 'ииаам', 'книга', 'гамма' являются словами в русском алфавите, а также в шестибуквенном алфавите {к, н, и, г, а, м}. Элементарным актом преобразования слов в алгоритмических процессах, задаваемых Н. а., является т. н. операция 'подстановки вместо первого вхождения'. Пусть Р , Q , R - слова в некотором алфавите. Результатом подстановки Q вместо первого вхождения Р в R называется слово å ( R , Р , Q ), получаемое следующим образом. Если Р входит в R , т.е. R представимо в виде S 1 PS2 , то среди таких представлений отыскивается представление с наиболее коротким словом S 1 и полагается å ( R , Р , Q ) S1QS2. Если же Р не входит в R , то å ( R , Р , Q ) R . Так, å (гамма, а, е) гемма.
Для задания Н. а. необходимо фиксировать некоторый алфавит А , не содержащий букв '-' и ' T ', и упорядоченный список слов вида Р - Q (простая формула подстановки) или Р -T Q (заключит. формула подстановки), где Р и Q - слова в А . Формулы подстановок принято записывать друг под другом в порядке следования, объединяя их слева фигурной скобкой. Получающаяся фигура называется схемой Н. а. Исходными данными и результатами работы Н. а. являются слова в А (сам Н. а. называется Н. а. в алфавите А ). Процесс применения к слову R Н. а. со схемой вида
где d i (1 £ i £ n )означает '-' или '-', разворачивается следующим образом. Отыскивается наименьшее i , при котором Pi входит в R . Если все Pi не входят в R , то работа заканчивается и её результатом считается R . Если требуемое i найдено, то переходят к слову å ( R , Pi , Qi ). При этом в случае, если использованная формула подстановки Pi d iQi была заключительной (d i - ), работа заканчивается и результатом считается å ( R , Pi , Qi ). Если же формула Pi d iQi - простая, то описанная процедура повторяется с заменой R на å ( R , R i , Qi ).
Пример. Натуральные числа можно рассматривать как слова в алфавите {О, 1} вида 0, 01, 01l,... Н. а. в этом алфавите со схемами {0 - T 01 и {1- переводят каждое натуральное число п соответственно в n + 1 и в 0 .
Множество всех Н. а. замкнуто относительно известных способов комбинирования алгоритмов. Например, по любым двум Н. а. и можно построить Н. а. , являющийся композицией и , т. е. реализующий следующий интуитивный алгоритм: 'сначала выполнить алгоритм , затем к результату применять '.
Соотношение между интуитивными алгоритмами и Н. а. описывается выдвинутым А. А. Марковым принципом нормализации: всякий алгоритм, перерабатывающий слова в данном алфавите А в слова в этом же алфавите, может быть реализован посредством Н. а. в некотором расширении А . [Легко указать очень простые алгоритмы в А , не реализуемые Н. а. в A ; с другой стороны, всегда можно ограничиться двухбуквенным (и даже однобуквенным) расширением A .] Принцип нормализации эквивалентен тезису Чёрча и, аналогично последнему, не может быть доказан из-за неточности интуитивной концепции алгоритма.
Лит.: Марков А. А., Теория алгорифмов, М. - Л., 1954 (Тр. Математического института АН СССР, т. 42); Мендельсон Э., Введение в математическую логику, пер. с англ., М., 1971.
Б. А. Кушнер.