Рассмотрим машину R , программа которой состоит из всех команд машины S и еще двух команд q01 → q01 и q00 → q0/ 0.

Здесь q0 — не заключительное, а q0/ — заключительное состоя-

ние. Если машина R самоприменима, то, начав работу со своего кода, она, в силу команд машины S придет в состояние (*). Затем в силу команды q01 → q01 она будет работать бесконечно. Это

значит, что R несамоприменима. Противоречие. Точно так же, если R несамоприменима, она придет сначала в состояние (**), а

затем остановится в силу команды q00 → q0/ 0. Значит, R самоприменима. Полученное противоречие и доказывает теорему.

3.3. Рекурсивные функции. Тезис Чёрча

Все известные примеры алгоритмов можно свести к вопросу вычисления значений подходящей функции. Естественно назвать функцию, значения которой могут находиться с помощью некоторого алгоритма, вычислимой функцией. Таким образом, вычислимая функция — это такая функция, для которой существует алгоритм, вычисляющий ее значения (вычисление функции происходит последовательно по определенным, заранее заданным, правилам и инструкциям).

Рассмотрим функции f	: +n → +, где	+ ={0, 1, 2, }.
Частичными числовыми функциями
f (x1, , xn ),	xi + (1≤i ≤n),

называют функции, определенные не на всех наборах

(x1, , xn ) +× × + = n+.

Назовем простейшими следующие всюду определенные функции:

71

o(x) =0 — нулевая функция;

s(x) = x +1 — функция следования;

Inm (x1, , xn )= xm, 1≤m ≤n, — функция выбора аргумента.

Все простейшие функции могут быть вычислены на машине Тьюринга:

1. o(x)=0:

q11→ q11R,

q10 →q20L,

q21→ q20L, q20 → q01S.

2. s(x)= x +1:

q11→ q11R,

q10 →q21L,

q21→ q21L, q20 → q00R.

3. f	(	x, y	= y,	0 1 1 ... 1	0 1 1 ... 1 0	→ 0 1 1 ... 1 0:
		)
				q1 x+1	y+1	q0 y+1

q11→ q10R, q10 →q00R.

Определим операции, которые из простейших строят новые функции.

72

xn+1.

Операция суперпозиции

Пусть даны функция f (y1, , ym ) от m аргументов и

функции g1(x1, , xn ), , gm (x1, , xn ) от n аргументов. Функция

F (x1, , xn ) = f (g1(x1, , xn ), , gm(x1, , xn ))

называется суперпозицией функций f и g1, , gm .

Примеры

1.s(o(x)) =1;

2.s(s(x)) =(x +1) +1= x +2.

Операция примитивной рекурсии

Пусть при n ≥1 даны какие-либо две функции g(x1, , xn ) и h(x1, , xn, xn+1, xn+2 ). Определим третью функцию

f (x1, , xn, xn+1)

по следующей схеме (схеме примитивной рекурсии):

		f (x , , x , 0) = g(x , , x					),
		1	n		1	n
f (x , , x , y+1) = h(x , , x , y, f (x , , x , y)).
	1	n		1	n	1	n

Эти равенства однозначно определяют функцию f . Говорят, что функция f получена из функций g и h с помощью операции примитивной рекурсии по переменной

При n =0 схема примитивной рекурсии имеет следующий вид:

73

		f (0) = a,
			(	)
	f (y+1) = h
				y, f (y) ,

где a — константа (число из множества + ={0, 1, 2, }). Функции, которые могут быть получены из простейших

функций o, s, Inm с помощью конечного числа применений опе-

раций суперпозиции и примитивной рекурсии, называются при-

митивно рекурсивными.

Операция минимизации

Пусть f (x1, x2, , xn ) ( xi +) — некоторая частичная чи-

словая функция.

Операция минимизации по i-й переменной функции f (x1, x2, , xn ) обозначается

g(x1, x2, , xn )=µy (f (x1, x2, , xi−1, y, xi+1, , xn ) = xi )

иопределяется следующим образом.

Пусть (x1, x2, , xn ) — произвольный набор чисел из множества + ={0, 1, 2, }. Рассмотрим соотношение

f (x1, x2, , xi−1, y, xi+1, , xn ) = xi ,

(*)

которое будем рассматривать, как уравнение относительно y. Это уравнение будем решать подбором, подставляя вместо y последовательно числа 0, 1, 2, . Возможны случаи:

1)На некотором шаге левая часть соотношения (*) не определена. В этом случае считаем, что на наборе

(x1, x2, , xn ) операция минимизации не определена.

74

2)На каждом шаге левая часть соотношения (*) определена, но ни при каких y равенство не выполняется. В

этом случае также считаем, что на наборе (x1, x2, , xn ) операция минимизации не определена.

3) Левая часть соотношения (*) определена при y =0, y =1, , y = y0 −1, y = y0, но при y < y0 равенство (*)

не выполнялось, а при y = y0 оно выполняется. В этом

случае полагаем g(x1, x2, , xn )= y0, т. е. число y0 считается значением операции минимизации на набо-

ре (x1, x2, , xn ).

Функции, которые могут быть получены из простейших функций o, s, Inm с помощью конечного числа применений опе-

раций суперпозиции, примитивной рекурсии и минимизации на-

зываются частично рекурсивными.

Общерекурсивные функции — это подмножество частично рекурсивных функций, определенных для всех значений аргументов.

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

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

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

Для любой частично рекурсивной функции можно указать алгоритм вычисления ее значений, т. е. все частично рекурсивные функции суть вычислимые функции. Обращение этого высказывания носит название тезиса Чёрча.

75