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

Алгоритмическая система Маркова строится по тем же принципам, что и МТ, но носит более простой и интуитивно понятный характер.

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

Пусть Х – некоторый конечный алфавит, F(X) – слова алфавита, Нормальные алгорифмы Маркова - student2.ru - пустое слово. Если Нормальные алгорифмы Маркова - student2.ru , то выражения Нормальные алгорифмы Маркова - student2.ru и Нормальные алгорифмы Маркова - student2.ru называются формулами подстановки в алфавите Х:

Нормальные алгорифмы Маркова - student2.ru - простая подстановка;

Нормальные алгорифмы Маркова - student2.ru - окончательная подстановка.

Символы → и . не принадлежат Х.

Слова p и q могут быть пустыми.

Строка R входит в строку L, если L имеет вид L1RL2. Подстановка применима к слову, если строка соответствующая левой части подстановки входит в слово. Применение заключается в замене в преобразующем слове левой строки – правой:

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

Механизм работы НАМ:

Дано преобразуемое слово – цепочка символов фиксированного алфавита и нормальная схема подстановок, содержащая фиксированную последовательность простых и заключительных подстановок.

1) Слово всегда просматривается слева направо. Схема подстановок просматривается, начиная с первой подстановки, и, если подстановку можно применить, то она применяется к самому левому вхождению этой строки в преобразуемое слово.

2) Работа алгоритма заканчивается если:

· ни одна из подстановок не применима,

· использована заключительная подстановка.

Может возникнуть ситуация, когда процесс не закончится никогда. В этом случае считают, что алгоритм не применим к слову.

Пример.

Х={x,y,z};

Нормальная схема подстановок:

xx ® y

xy ® x

yzy ® x

zz ®. z

yy ® x

Преобразуемое слово:

xxxyyyzzz →yxyyyzzz→yxyyzzz →yxyzzz→yxzzz→yxzz

Пример.

X={А,Б,В,Г,…,Я};

Нормальная схема подстановок:

Х®К

М®Р

КА®ЛОН

РУ®.С

Преобразуемое слово:

МУХА®МУКА®РУКА®РУЛОН®СЛОН

Пример 9:

X={a,b};

Нормальная схема подстановок:

a→.e

b→b

Преобразуемое слово:

bbbbbb - схема не применима.

Преобразуемое слово:

abab →bab

Пример.

Х={х,у,х-1-1};

Нормальная схема подстановок:

х х-1→е

х-1х→е

у у-1→е

у-1у→е

Преобразуемое слово:

ххухуу-1х-1ух→ ххухх-1ух→ ххуух

Пример 10:

Х={x1, …,xn};

Нормальная схема подстановок:

x1→e

x2→e

xn→e

Преобразуемое слово переписывается в пустое.

Пусть R и Q нормальные алгорифмы над алфавитом Х и pÎF(x). Запись Нормальные алгорифмы Маркова - student2.ru означает, что или оба алгорифма R и Q не применимы к слову p, или оба применимы и Нормальные алгорифмы Маркова - student2.ru .

Два алгорифма R и Q называют эквивалентными относительно алфавита Х, если Нормальные алгорифмы Маркова - student2.ru каждый раз, когда pÎF(x) и хотя бы одно из слов R(p) или Q(p) определено и тоже принадлежит F(x).

Если для всех pÎF(x) Нормальные алгорифмы Маркова - student2.ru , то R и Q называются полностью эквивалентными.

Пусть X={1}, а Нормальные алгорифмы Маркова - student2.ru . Тогда всякое натуральное число n можно записать в виде слова в алфавите Нормальные алгорифмы Маркова - student2.ru :

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

Поставим в соответствие вектору (n1, n2, …nk), где n1, n2, …nk – натуральные числа, слово в алфавите Нормальные алгорифмы Маркова - student2.ru вида Нормальные алгорифмы Маркова - student2.ru Нормальные алгорифмы Маркова - student2.ru , которое обозначим Нормальные алгорифмы Маркова - student2.ru . Например, вектору Нормальные алгорифмы Маркова - student2.ru соответствует слово 11111*1*111.

Пусть f: Nk→N – некоторая частичная функция и Rf обозначает алгорифм в алфавите Нормальные алгорифмы Маркова - student2.ru такой, что

Нормальные алгорифмы Маркова - student2.ru тогда и только тогда, когда хотя бы одна из частей равенства определена. При этом считается, что алгорифм Rf не применим к словам отличным от вида Нормальные алгорифмы Маркова - student2.ru .

Функция f называется частично определимой по Маркову, если существует нормальный алгорифм Q над Нормальные алгорифмы Маркова - student2.ru полностью эквивалентный Rf над Нормальные алгорифмы Маркова - student2.ru . Если функция определена полностью, то ее называют просто вычислимой по Маркову.

Теорема: Простейшие функции O(x)=0, S(x)=x+1 и Im(x1,x2,…,xn)=xm вычислимы по Маркову.

Доказательство сводится к построению соответствующих алгорифмов.

1.Функцию O(x)=0 реализует следующий алгорифм R0:

Нормальные алгорифмы Маркова - student2.ru ={1,*}, Нормальные алгорифмы Маркова - student2.ru ;

Нормальная схема подстановок:

*→* (1)

α11→ α1 (2)

α1→.1 (3)

е→ α (4)

Преобразуемое слово:

р=111…11.

Тогда по формуле (4) получаем р= α 11…11.

Применим формулу (2) и получим: р= α 11…11→ α 1…11→ α 1.

Применяем формулу (3) и получаем α 1→1.

Так как 1 – это Нормальные алгорифмы Маркова - student2.ru в алфавите Х, то R0 и является искомым алгоритмом.

2. Функцию S(x)=x+1 реализует следующий алгорифм Rs:

Нормальные алгорифмы Маркова - student2.ru ={1,*}, Нормальные алгорифмы Маркова - student2.ru ;

Нормальная схема подстановок:

*→* (1)

α1→.11 (2)

е→ α (3)

Преобразуемое слово:

р=111…11.

Тогда по формуле (3) получаем р= α 11…11 (n единиц).

Применим формулу (2) и получим: р= 111…11 (n+1 единица). Так как всякое натуральное число n можно записать в виде слова в алфавите Нормальные алгорифмы Маркова - student2.ru :

Нормальные алгорифмы Маркова - student2.ru , то мы реализовали алгоритм RS(n)=n+1.

Этот алгоритм применим только к тем словам, которые являются натуральными числами.

3. Алгорифм RI имеет более сложную структуру, с ним можно ознакомиться самостоятельно в учебнике «Лекции по дискретной математике», авторы: Капитонова Ю.В. и др.

Теорема: Всякая частично рекурсивная функция частично рекурсивна по Маркову.

Обратная теорема: всякая частично вычислимая по Маркову функция является частично рекурсивной.

Наши рекомендации