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

В терминах нормальных алгорифмов формализация понятия «алгоритм» была предложена советским математиком Андреем Андреевичем Марковым в 1951 году. Краткое изложение теории нормальных алгорифмов выглядит так.

А.А.Марков

Пусть имеется произвольный алфавит A={a₁, a₂, a₃,…a_m}, не содержащий пустой буквы[3] и символов →, Þ. Через A^* будем обозначать множество слов над алфавитом A. Считается, что пустое слово l входит в любое слово перед каждой его буквой. Это означает, например, что a₁a₂a₃a₅ и la₁la₂la₃la₅ – две записи одного и того же слова. Тот факт, что слово bÎA^* входит в слово aÎ A^*[4], фиксируется так: bÍa.

В теории нормальных алгоритмов над словами определяются, операции, именуемые подстановками, в общем виде записываемыми в виде:

h→x (h,xÎ A^*) (1)

hÞx (h,xÎ A^*) (2)

При этом подстановка (1) называется простой, подстановка (2) – заключительной.

Результатом применения подстановки h→x к слову aÎ A^* называют слово bÎA^*_, полученное путем замены в слове a первого вхождения слова h на слово h (в этом случае говорят, что подстановка h→x является активной на слове a). Если слово h не входит в слово a, то говорят, что подстановка h→x не является активной на слове a. Например, если a=a₁a₂a₃a₅, h=a₂a₃, x=a₅, то результатом подстановки h→x на слове a будет слово b= a₁a₅a_5.

Определение 2.2.1. Линейно упорядоченная конечная последовательность подстановок вида (1) – (2) называется функциональной схемой нормального алгорифма.

Таким образом, нормальный алгорифм M задается алфавитом и списком подстановок. Обычно этот список записывают в «столбик», считая упорядоченным сверху вниз.

Применение нормального алгорифма M кслову a предполагает следующий порядок действий.

1. Задается исходное слово a₀.

2. Полагается, что a=a₀.

3. Просматривается сверху вниз список подстановок в поиске первой из них, активной на слове a.

4. Если подстановок, активных на слове a нет, то результатом работы нормального алгорифма над словом a считается слово a (M(a)=a).

Процесс применения алгорифма M к слову a оканчивается.

5. Если найденная активная на слове a подстановка оказывается заключительной, то она применяется к слову a. Результат ее применения считается результатом применения всего алгорифма M к слову a.

Процесс применения алгорифма M к слову a оканчивается.

6. Если найденная активная на слове a подстановка оказывается простой, то она применяется к слову a (результат применения обозначается как b).

7. Полагается, что a=b и осуществляется возврат к пункту 3.

Если нормальный алгорифм оканчивается в пунктах 4 – 5, то говорят, что он применим к слову a₀. В противном случае, если процесс никогда не оканчивается, говорят, что нормальный алгорифм M не применим к слову a_0.

При этом возможны различные варианты.

Так, например алгорифм M₁ в алфавите A={0,1} c функциональной схемой: