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

одно из современных уточнений понятия Алгоритма, получившее распространение в исследованиях по конструктивной математике (См. Конструктивная математика). Предложено в 1950 А. А. Марковым, впервые систематически и строго построившим на основе этого уточнения общую алгоритмов теорию (См. Алгоритмов теория). Н. А. Эквивалентны частично-рекурсивным функциям (см. Рекурсивные функции), а следовательно, и Тьюринга машинам. Концепция Н. А. Специально приспособлена для реализации алгоритмов, действующих над словами в тех или иных алфавитах. При этом под алфавитом в математике понимается любой конечный набор четко отличимых друг от друга графических символов (букв), а под словом в данном алфавите — произвольная конечная цепочка букв этого алфавита.

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

Так, ∑ (гамма, а, е) = гемма. Для задания Н. А. где δi (1 ≤ i ≤ n) означает «→» или «→», разворачивается следующим образом. Отыскивается наименьшее i, при котором Pi входит в R. Если все Pi не входят в R, то работа .