2. Нормальные алгорифмы Маркова
|
В терминах нормальных алгорифмов формализация понятия «алгоритм» была предложена советским математиком Андреем Андреевичем Марковым в 1951 году. Краткое изложение теории нормальных алгорифмов выглядит так. |
А.А.Марков |
Пусть имеется произвольный алфавит A={a1, a2, a3,…am}, не содержащий пустой буквы1 и символов →, . Через A* будем обозначать множество слов над алфавитом A. Считается, что пустое слово входит в любое слово перед каждой его буквой. Это означает, например, что a1a2a3a5 и a1a2a3a5 – две записи одного и того же слова. Тот факт, что слово A* входит в слово A*2, фиксируется так: .
В теории нормальных алгоритмов над словами определяются, операции, именуемые подстановками, в общем виде записываемыми в виде:
→ (, A*) (1)
(, A*) (2)
При этом подстановка (1) называется простой, подстановка (2) – заключительной.
Результатом применения подстановки → к слову A* называют слово A*, полученное путем замены в слове первого вхождения слова на слово (в этом случае говорят, что подстановка → является активной на слове ). Если слово не входит в слово , то говорят, что подстановка → не является активной на слове . Например, если =a1a2a3a5, =a2a3, =a5, то результатом подстановки → на слове будет слово = a1a5a5.
Определение 2.2.1. Линейно упорядоченная конечная последовательность подстановок вида (1) – (2) называется функциональной схемой нормального алгорифма.
Таким образом, нормальный алгорифм M задается алфавитом и списком подстановок. Обычно этот список записывают в «столбик», считая упорядоченным сверху вниз.
Применение нормального алгорифма M к слову предполагает следующий порядок действий.
1. Задается исходное слово 0.
2. Полагается, что =0.
3. Просматривается сверху вниз список подстановок в поиске первой из них, активной на слове .
4. Если подстановок, активных на слове нет, то результатом работы нормального алгорифма над словом считается слово (M()=).
Процесс применения алгорифма M к слову оканчивается.
5. Если найденная активная на слове подстановка оказывается заключительной, то она применяется к слову . Результат ее применения считается результатом применения всего алгорифма M к слову .
Процесс применения алгорифма M к слову оканчивается.
6. Если найденная активная на слове подстановка оказывается простой, то она применяется к слову (результат применения обозначается как ).
7. Полагается, что = и осуществляется возврат к пункту 3.
Если нормальный алгорифм оканчивается в пунктах 4 – 5, то говорят, что он применим к слову 0. В противном случае, если процесс никогда не оканчивается, говорят, что нормальный алгорифм M не применим к слову 0.
При этом возможны различные варианты.
Так, например алгорифм M1 в алфавите A={0,1} c функциональной схемой:
010 1
10 → 00
1→ 11,
применим к словам:
а) 0=00 (M1(00)=00 – в функциональной схеме нет ни одной активной подстановки);
б) 0=110 (M1(110)=000 – дважды применяется вторая подстановка);
в) 0=010 (M1(010)=1 – применяется заключительная подстановка.
Этот же алгорифм не применим к словам: 0=01; 0=1; 0=11 и т.д.
Вот еще два примера, заимствованных нами из [ ].
Пример 2.2.1. Алгорифм M2 вычисления суммы чисел, записанных в унарной системе счисления в алфавите A1={1,+} в виде 11+1 или 111+11+1 и т.п., работающий в алфавите A2=A1{}, определяется следующей функциональной схемой:
+ →
1 → 1
→ .
Пример 2.2.2. Алгорифм M3, работающий над алфавитом A1={0,1} в алфавите A2=A1{, } и прибавляющий 1 к двоичному числу, имеет следующую функциональную схему:
1 → 1
0 → 0
→