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

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

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

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

обозначается				. Алфавит А называется расширением алфавита В, если
В		А.
		Очевидно, что в этом случае всякое слово в алфавите В является также
словом в алфавите А.
		Если Р обозначает слово			. . .	и Q обозначает слово			. . .
	,	то PQ обозначает объединение				. . .	. . .	. В частности,

Р∆ = ∆Р = Р; кроме того (Р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 находятся в описанном отношении, коротко запи-

шем в виде:

(алгоритм)

:

, если

m→(·)Qm – простая формула подстановки;

или

:

·

, если m→(·)Qm – заключительная формула подстановки.

В

что алгоритм

просто переводит слово P

первом случае говорят,

в слово

,

во втором случае говорят, что алгоритм

заключительно пере-

водит слово P в слово .

Пусть далее

:

означает,

что существует такая последователь-

ность

0,

1 . . .,

слов в алфавите А, что

0

=

;

= ;

:

+1

для

j = 0,1 . . .

– 2, причем либо

:

-1

, либо

:

–1

последнем

R).

(в

случае вместо

пишут

: P

∙

Положим

:

∙

R,

теперь U(P) = R тогда и только тогда, когда либо U: P

либо U: P

R и U: 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, перерабатывающий всякое слово в алфавите А в пустое слово.

Например	U: a a a a a		a1a2a1a3 a2a1a3				a2a3		a3		и,
Вопрос	. Следовательно1 2 1 3 0	, U(a1a2a1a3a0) =
наконец, 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

c) Доказать, что функция частично-рекурсивная, используя оператор минимизации.

Дана функция

f(x, y) = x y = xy , если х кратно у, и не определена, если х делится

на у с остатком

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

Рассмотрим функцию g x, y, z x yz . Эта функция по доказанному в рассмотренном выше примере есть ПРФ.

Тогда f(x, y) = x y = µz(g) = xy , если х кратно у, и не определена, если

х делится на у с остатком.

Здесь µz(g) – оператор минимизации.

Действительно, если x кратно y, то = xy – наименьший корень уравнения g(x, y, z) = 0, так как:

g(x, y,	– 1) =	x y		x						y 0
								1
					y
g(x, y,	– 2) =			x
			x y					2		2y 0
						y

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

		g(x, y, 0) = x ≠ 0, если x ≠ 0, если же x = 0, то						=	x
										, = 0.
									y
Если же x делится на y с остатком, то ни при каком z								N = {0, 1, 2 . . .}
g(x, y, z) =		x yz		0,	т. е. оператор µz(g) не определен;	таким образом мы

доказали, что f(x, y) получена оператором минимизации из ПРФ, т. е. является частично-рекурсивной.

d)Доказать, что функция f(x) вычислима по Тьюрингу, построив МТ

сзаданным внешним алфавитом, вычисляющую данную функцию:

f(x) = x + 3; алфавит {0, 1, 2, a0}, где а0 – символ пустой клетки. Очевидно, что данный алфавит определяет запись чисел в троичной

системе исчисления.

Для такой функции нужны следующие внутренние состояния, т. е. реакции машины на символы внешнего алфавита: q1 – прибавление 3; q2 – прибавление (запоминание) 1 и, наконец, q3 – сохранение данного символа и переход к следующему; q0 – как обычно, символ остановки машины.

21