Материал: Красовская Т. Ф. Основы теории алгоритмов

Определение. МТ называется самоприменимой, если она применима к своему номеру N(M), т. е. если она начинает работу со своим кодом и через конечное число шагов останавливается (заканчивает работу).

Очевидный пример несамоприменимой машины – если в правых частях команд не встречается q0 – stop – состояние. Такая машина не применима ни к какому слову, а не только к N(M).

Рассмотрим алгоритмическую проблему самоприменимости, т. е. существует ли алгоритм, который по любому N(M) устанавливает, самоприменима ли она или нет. Согласно Тьюрингу это означает, существует ли такая МТ, которая была бы применима к кодам номеров всех МТ и в зависимости от того, самоприменима МТ или нет, имела бы различные заключительные конфигурации. Например, в случае самоприменимости МТ заключительная конфигурация имеет вид {00 10 0}, а в случае несамопри-

менимости {0 0 00 0}.

Теорема. Проблема самоприменимости алгоритмически неразрешима, т. е. не существует МТ, решающей эту проблему.

Доказательство. Предположим противное, что такая машина А существует. Тогда можно построить машину В, которая: 1) применима ко всем кодам номеров несамоприменимых машин, т. е. по номеру устанавливает, что машина несамоприменима; 2) не применима ко всем кодам номеров самоприменимых машин.

Действительно, машина В получается из А следующим образом: алфавит сохраняется неизменным; заключительное состояние q0 машины А считается незаключительным состоянием В, а заключительным состоянием В считается новое состояние , причем программа В состоит из всех команд А и еще двух команд:

1q0 -> 1Cq0

0q0 -> 0C

Очевидно, что В удовлетворяет требованиям 1) и 2), так как конфигурация 1 машины А означает, что установлена самоприменимость иссле-

дуемой МТ, а команда 1q0 -> 1Cq0 зацикливает программу, что означает, что В не применима к номеру самоприменимой МТ; в то же время заключительная конфигурация 0 машины А устанавливает несамоприме-

нимость МТ, а команда 0q0 -> 0C означает, что В применима к несамоприменимой МТ.

16

Итак, если В самоприменима, то она применима и к коду самоприменимой МТ, но тогда требование 2) не удовлетворено; если же В несамоприменима, то она не применима и к коду несамоприменимой МТ, но тогда не выполнено требование 1). Следовательно, мы пришли к противоречию, т. е. не существует машины А, решающей проблему самоприменимости.

Используя результат этой теоремы, можно доказать неразрешимость других алгоритмических проблем. Например, можно доказать теорему об алгоритмической неразрешимости проблемы применимости МТ к начальному слову, т. е. что не существует МТ (а следовательно, и алгоритма), разрешающей проблему установления по номеру N(M) и начальному слову X , применима ли МТ к X.

НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА

Определения. Будем называть алфавитом А всякое непустое конечное множество символов, а сами символы алфавита будем называть буквами. Словом в алфавите А называется всякая конечная последовательность букв алфавита А. Пустая последовательность букв называется пустым словом и

Р∆ = ∆Р = Р; кроме того (Р1Р2)Р3 = Р1(Р2Р3). Принято говорить, что слово Т входит в слово Q, если существуют такие (возможно, пустые) слова V и

W, что Q = WTV.

Алгоритмом U в алфавите А называется вычислимая функция, областью определения которой служит подмножество В А и значения которой есть слова из А. Если С А, т. е. С – расширение А, то всякий алгоритм в С называется алгоритмом над алфавитом А.

Пусть Р есть слово в алфавите А; говорят, что алгоритм U применим к слову Р, если Р содержится в области определения U.

Большинство известных алгоритмов можно разбить на некоторые простейшие шаги (одно из свойств алгоритма – элементарность каждого шага). Следуя А. А. Маркову, в качестве элементарной операции, на базе которой строятся алгоритмы, выделим подстановку одного слова вместо другого. Если Р и Q – слова в алфавите А, то выражение Р→Q называется простой

17

формулой подстановки в А, а Р→·Q называется заключительной формулой подстановки в А; при этом предполагается, что символы стрелка «→» и точка «·» не являются буквами алфавита А, а каждое слово Р и Q может

быть и пустым словом.

Пусть Р→(·) Q обозначает одну из формул подстановки P→Q или

P→·Q.

Конечный список формул подстановки в алфавите А:

P1→(·)Q1

P2→(·)Q2

. . . . . . . .

Pr→(·)Qr

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

Пусть Р – слово в алфавите А может быть одно из двух:

1)ни одно из слов Р1 Р2 . . . Рr не входит в слово Р (обозначается:

U : P );

2)среди слов Р1 Р2 . . . Рr существуют такие, которые входят в Р.

Пусть m – наименьшее целое число из 1, 2, . . ., r такое, что Рm входит в Р, и пусть R – слово, которое получается, если самое левое вхождение слова Рm в слово Р заменить словом Qm.

Тот факт, что Р и R находятся в описанном отношении, коротко запи-

мальный алгоритм Маркова.

18

Таким образом, работу алгоритма U можно описать следующим образом: пусть дано слово Р в алфавите А. Находим первую в схеме алгоритма

U формулу подстановки Pm→(·)Qm такую, что Рm входит в Р. Совершаем подстановку слова Qm вместо самого левого вхождения слова Pm в Р. Пусть R1 – результат такой подстановки. Если Pm→(·)Qm – заключительная форма подстановки, то работа алгоритма заканчивается, и его значением является R1; если же формула подстановки Pm→(·)Qm – простая, то к R1 применим тот же поиск, который был только что применен к Р, и так далее. Если на конечном этапе будет получено такое слово Ri , что U: Ri , т. е. ни одно из слов P1 . . . Pr не входит в Ri, то работа алгоритма заканчивается, и Ri будет его значением. Если же описанный процесс на конечном этапе не заканчивается, то говорят, что алгоритм U не применим к данному слову Р.

Пример 1. Пусть А есть алфавит {b, c}. Рассмотрим схему b → ; c→c. Определяемый этой схемой нормальный алгоритм U перерабатывает всякое слово Р в алфавите А, содержащее хотя бы одно вхождение буквы b, в слово, которое получается вычеркиванием в Р самого левого вхождения буквы b.

Если P = ccbbc, то P→·Q, где Q = ccbc. Данный алгоритм U не применим к пустым словам, не содержащим буквы b, так как простые подстановки с→с будут перерабатывать эти слова в себя самих, но тогда всегда Р→Р, и мы не приходим к заключительной подстановке, т. е. процесс будет продолжаться бесконечно.

Если же рассмотреть несколько измененную схему b→ ; c→·c, то алгоритм применительно к слову Р = ccbbc сработает так: U: ccbbc ccbc ccc ccc

Пример 2. Пусть А есть алфавит {a0, a1 . . . an}. Рассмотрим схему:i (ai → ), ai A. Эта схема определяет нормальный алгоритм U, перерабатывающий всякое слово в алфавите А в пустое слово.

с точки зрения определения нормального алгоритма Маркова можно поставить так: если не существует нормального алгоритма Маркова, решающего данную массовую проблему, то данная массовая проблема алгоритмически не разрешима.

В частности американский математик Чёрч еще в 1936 году доказал одну из первых теорем такого рода.

19

Теорема Чёрча. Проблема распознавания выводимости алгоритмически неразрешима. Проблема распознавания выводимости: для любых двух формул А и В в логическом исчислении узнать, существует ли дедуктивная цепочка, ведущая от А к В, или нет.

Решение этой проблемы понимается в смысле вопроса о существовании алгоритма, дающего ответ при любых А и В.

ПРИМЕР ВЫПОЛНЕНИЯ ИНДИВИДУАЛЬНОГО ЗАДАНИЯ

a) Доказать, что функция f(x, y) = max {x, 2y} есть ПРФ.

Очевидно, что f(x, y) можно записать в виде: f(x, y) = max {x, 2y} = x +

+(2y o x) = {2y если 2y ≥ x и x, если 2y < x

Вданном случае проще провести рекурсию по x:

f(0, y) = 0 + (2y o 0) = 2y , т. е. g(y) – ПРФ

f(x + 1, y) = x + 1 + (2y o (x + 1)) = x + 1 + (2y o x) o 1 = 1 + x + (2y o x) o 1 = = 1 + f(x, y) o 1

Тогда можно ввести функцию h(x, y, z) = 1 + (z o 1) – ПРФ, так как она есть сумма 1 и (z o 1) – двух ПРФ.

Тогда схема примитивной рекурсии для f(x, y):

f(0, y) = g(y) = 2y; h(x, y, z) = 1 +(zo 1); f(x + 1, y) = h(x, y, f(x, y)),

т. е. f(x, y) – ПРФ, так как она получена по схеме ПР.

b) Найти (n + 1)-местную функцию с помощью заданного оператора примитивной рекурсии: n = 2 g(x, y) = xy h(x, y, z, t) = xy(z + 1)t f(x, y, z) =?

Схема примитивной рекурсии получается такой:

f(x, y, 0) = g(x, y) = xy

f(x, y, z + 1) = h(x, y, z, f(x, y, z)) f(x, y, 1) = xy·1·xy = 1·(xy)2

f(x, y, 2) = xy·2·1·(xy)2 = 2!(xy)3 f(x, y, 3) = xy·3·2!(xy)3 = 3!(xy)4

. . . . . . . . . . . . . . . . . .

Или в общем виде:

f(x, y, z) = xyz · f(x, y, z – 1) = xyz · xy(z – 1) · f(x, y, z – 2) = = (xy)2z(z – 1) · xy·(z – 2) · f(x, y, z – 3) = (xy)3 · z·(z – 1) ·

· (z – 2) · xy · (z – 3) · f(x, y, z – 4) = . . . = (xy)z · z! · f(x, y, 0) = = (xy)z + 1 · z!

Итак, данный оператор примитивной рекурсии задает вычислимую

функцию

f(x, y, z) = z!(xy)z + 1.

20