Общие сведения. Норма́льный алгори́тм Ма́ркова (НАМ, также марковский алгоритм) – один из стандартных способов формального определения понятия алгоритма

Норма́льный алгори́тм Ма́ркова (НАМ, также марковский алгоритм) – один из стандартных способов формального определения понятия алгоритма (другой известный способ – машина Тьюринга). Понятие нормального алгоритма введено А.А. Марковым (младшим) в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений. Традиционное написание и произношение слова «алгорифм» в этом термине также восходит к его автору, многие годы читавшему курс математической логики на механико-математическом факультете МГУ.

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