Нормальные алгоритмы Маркова

конце 1940-х годов.
При изучении разрешимости некоторых задач алгебры, он предложил новую модель вычислений, которую назвал нормальными алгорифмами.

Андрей Андреевич Марков (младший) (22.09.1903-11.10.1979) – советский математик, сын известного русского математика А.А.Маркова, основоположник советской школы конструктивной математики, автор понятия нормального алгоритма (1947 г.)

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

машин Тьюринга НАМ — это "чистый” алгоритм, который не связан ни с каким "аппаратным обеспечением” (лентой, кареткой и т.п.).
НАМ преобразует одно слово (цепочку символов некоторого алфавита) в другое и задается алфавитом и системой подстановок.

последовательность букв – словами в данном алфавите
Для удобства рассуждений допускается пустое слово, которые обозначим Λ
Слова будем обозначать буквами Р, Q, R и с индексами

где α и β – любые слова (возможно, и пустые).
При этом α называется левой частью формулы, а β – правой частью.
Сама подстановка (как действие) задается формулой подстановки и применяется к некоторому слову Р.
Суть операции сводится к тому, что в слове Р отыскивается часть, совпадающая с левой частью этой формулы (т.е. с α), и она заменяется на правую часть формулы (т.е. на β). При этом остальные части слова Р (слева и справа от α) не меняются. Получившееся слово R называют результатом подстановки.
Условно это можно изобразить так:

сводится к выполнению последовательности шагов. На каждом шаге входящие в НАМ формулы подстановки просматриваются сверху вниз и выбирается первая из формул, применимых к входному слову Р, т.е. самая верхняя из тех, левая часть которых входит в Р. Далее выполняется подстановка согласно найденной формуле. Получается новое слово Р′.
На следующем шаге это слово Р′ берется за исходное и к нему применяется та же самая процедура, т.е. формулы снова просматриваются сверху вниз начиная с самой верхней и ищется первая формула, применимая к слову Р′, после чего выполняется соответствующая подстановка и получается новое слово Р′′. И так далее: Р → Р′ → Р′′ → …
?Следует обратить особое внимание на тот факт, что на каждом шаге формулы в НАМ всегда просматриваются начиная с самой первой.
Необходимые уточнения:
1. Если на очередном шаге была применена обычная формула (α→β), то работа НАМ продолжается.
2. Если же на очередном шаге была применена заключительная формула (α ו→ β), то после её применения работа НАМ прекращается. То слово, которое получилось в этот момент, и есть выходное слово, т.е. результат применения НАМ к входному слову.

находят первое вхождение слова Р и, не изменяя остальных частей слова R, заменяют в нем это вхождение словом Q

Рассмотрим упорядоченную пару слов (Р,Q)

R
2) Если первого вхождения слова Р в слово R нет (и, следовательно, вообще нет ни одного вхождения Р в R), то считается что марковская подстановка (Р,Q) не применима к слову R

(Λ,Λ)

называют формулой подстановки (Р,Q)
Различают простые подстановки Р → Q и заключительные подстановки Р ו→ Q