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

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

А.А.Марков

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

010 Þ 1

10 → 00

1→ 11,

применим к словам:

а) a₀=00 (M₁ (00)=00 – в функциональной схеме нет ни одной активной подстановки);

б) a₀=110 (M₁ (110)=000 – дважды применяется вторая подстановка);

в) a₀=010 (M₁ (010)=1 – применяется заключительная подстановка.

Этот же алгорифм не применим к словам: a₀=01; a₀=1; a₀=11 и т.д.

Вот еще два примера, заимствованных нами из [ ].

Пример 2.2.1. Алгорифм M₂ вычисления суммы чисел, записанных в унарной системе счисления в алфавите A₁ = {1,+} в виде 11+1 или 111+11+1 и т.п., работающий в алфавите A₂ = A₁È {Q}, определяется следующей функциональной схемой:

Q+ → Q

Q1 → 1Q

Q Þ l

l → Q.

Пример 2.2.2. Алгорифм M_3, работающий над алфавитом A₁ = {0,1} в алфавите A₂ = A₁È {Q, D} и прибавляющий 1 к двоичному числу, имеет следующую функциональную схему:

Q1 → 1Q

Q0 → 0Q

Q → D

1D → D0

0D Þ 1

D Þ 1

l → Q.

Дата добавления: 2014-01-06