Работа нормального алгоритма Маркова

Исходное слово просматривается слева направо с целью выявления вхождения первого правила подстановки. Как только находится первое вхождение первого правила подстановки, оно заменяется по этому правилу и исходное слово снова просматривается с первого символа по первому правилу подстановки.

После того, как первое правило больше не встречается в данном слове, аналогично применяется второе правило подстановки.

Работа алгоритма заканчивается тогда, когда ни одна из подстановок не применима, либо использована заключительная подстановка.

ПРИМЕР

Построить нормальный алгоритм Маркова, стирающий последовательность единиц.

Нормальный алгоритм Маркова для данной задачи представляет собой две подстановки:

1.

2.

Первая подстановка стирает все единицы до последней. Вторая (заключительная) подстановка заменяет последнюю единицу пробелом .

Тезис А. Черча. Если функция выполнима, то она может быть представлена в виде нормального алгоритма Маркова.

Заключительный тезис А. Черча. Если функция выполнима, то она может быть представлена в виде либо общерекурсивной функции, либо. машины Тьюринга, либо в виде нормального алгоритма Маркова.

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