НОРМАЛЬНЫЕ АЛГОРИФМЫ, нормальные алгоритмы

— класс словарных алгоритмов, т. е. алгоритмов, применимых к словам некоторого алфавита. Ввел их сов. математик А. А. Марков (р. 1903). Всякий Н. а. вполне определяется указанием алфавита, в котором он действует, и схемы Н. а. Алфавитом Н. а. может служить произвольный конечный алфавит А. Формулами подстановок в алфавите А наз. выражения вида (простая подстановка) или (заключительная подстановка), где — некоторые слова в алфавите А, называемые соответственно левой и правой частями ф-лы подстановки (предполагается, что алфавит А не содержит букв

Каждый Н. а. в алфавите А имеет конечное число таких ф-л подстановок. Их записывают в виде списка. Этот список наз. схемой алгоритма.

Применение Н. а. к слову s заключается в следующем. В данном списке подстановок ищут первую из тех, в которой левая часть входит в слово s. Находят первое вхождение левой части этой ф-лы в s и вместо этого вхождения подставляют правую часть Это дает новое слово . С ним делают то же, что с s, и т. д. Этот процесс может оборваться сам собою на некотором слове, в которое не входит ни одна из левых частей подстановок, составляющих схему алгоритма. Кроме того, постулируют, что описанный выше процесс обрывается, когда к очередному слову применить одну из заключительных подстановок, т. е. вида

Если процесс заканчивается, то полученное последнее слово является результатом применения Н. а. к исходному слову s.

Доказано, что относительно осуществляемых ими преобразований, Н. а. совпадают с другими классами алгоритмов, введенными для уточнения интуитивного понятия алгоритма, напр., Тьюринга машинами. Аналогом Черча тезиса для Н. а. является следующий аринцип нормализации А. А. Маркова: всякий алгоритм в алфавите А вполне эквивалентен относительно .4 некоторому Н. а. над А. Задание алгоритмов в нормальном виде близко к понятию исчисления, и это чрезвычайно удобно в тех случаях, когда в исследуемом разделе математики или кибернетики понятие исчисления широко используют, как это имеет место, напр., в логике математической или лингвистике математической. Пользуясь понятием Н. а., А. А. Марков и др. доказали неразрешимость целого ряда алгоритм, проблем (см. Неразрешимые алгоритмические проблемы).

Лит.: Марков А. А. Теория алгорифмов. «Труды Математического института им. В. А. Стеклова АН СССР», 1954, т. 42. М. И. Кратко.