НОРМАЛЬНЫЙ АЛГОРИФМ

НОРМАЛЬНЫЙ АЛГОРИФМ одно из совр.
уточнений понятия алгоритма, получившее распространение в исследованиях
по конструктивной математике. Предложено в 1950 А. А. Марковым,
впервые
систематически и строго построившим на основе этого уточнения общую алгоритмов
теорию. Н. а. эквивалентны частично-рекурсивным функциям (см. Рекурсивные
функции), а следовательно, и Тьюринга машинам.

Концепция Н. а. специально приспособлена
для реализации алгоритмов, действующих над словами в тех или иных алфавитах.
При этом под алфавитом в математике понимается любой конечный набор чётко
отличимых друг от друга графических символов (букв), а под словом в данном
алфавите - произвольная конечная цепочка букв этого алфавита. Цепочка,
вовсе не содержащая букв, также считается словом в данном алфавите (пустое
слово). Напр., цепочки "ииаам", "книга", "гамма" являются словами в русском
алфавите, а также в шестибук-венном алфавите {к, н, и, г, а, м}. Элементарным
актом преобразования слов в алгоритмических процессах, задаваемых Н. а.,
является т. н. операция "подстановки вместо первого вхождения". Пусть Р,
Q, R - слова в нек-ром алфавите. Результатом подстановки Q вместо
первого вхождения Р в R наз. слово сумма (R, Р, Q), получаемое
след, образом. Если Р входит в R, т. е. R представимо в виде
Sпредставление с наиболее коротким словом S(К, Р, Q) = SР не входит в R,
то
сумма (R, Р, Q) = R. Так, сумма (гамма, а, е) = гемма.

Формулы подстановок принято записывать
друг под другом в порядке следования, объединяя их слева фигурной скобкой.
Получающаяся фигура наз. схемой Н. а. Исходными данными и результатами
работы Н. а. U являются слова в А (сам Н. а. U наз. Н. а. в алфавите
Л). Процесс применения к слову R H. а. U со схемой вида

А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я