Нормальный алгоритм Маркова
Математическое построение, предназначенное для уточнения понятия алгоритм.

Нормальный алгоритм Маркова задается алфавитом А и нормальной схемой подстановок.

Алфавит - конечное, непустое множество элементов называемых буквами. Различные сочетания букв образуют слова.

Нормальная схема подстановок - это конечный набор, состоящий из пар слов, где левое слово переходит в правое (но не наоборот).

Нормальным алгоритмом в алфавите А называется следующий алгоритм построения последовательности слов: в качестве начального слова берется само слово Р, и к нему применяют по порядку каждую пару из схемы подстановки. Если подстановка возможна, то ее осуществляют и начинают подстановки сначала. Если процесс обрывается (нет ни одной допустимой подстановки) на слове Q или приходит в конечную подстановку, то данный нормальный алгоритм преобразовал Р в Q.

Если есть задача: от Р перейти к Q и доказано, что нельзя построить нормальную схему, то имеет место алгоритмически неразрешимая задача.

Можно ли любой алгоритм представить в виде нормального алгоритма Маркова? На этот вопрос дается ответ в виде так называемого тезиса Маркова: всякий алгоритм в алфавите А представим в виде нормального алгоритма в этом же алфавите. Это тезис потому, что его невозможно доказать, т.к. в нем фигурируют с одной стороны, интуитивное расплывчатое понятие "всякий алгоритм", а с другой стороны - точное понятие "нормальный алгоритм".

Класс нормальных алгоритмов Маркова и класс алгоритмов представленных в форме машин Тьюринга (машин Поста) совпадают.

Назван по имени автора А. А. Маркова.