A08DPPMAT_UPS2006D00

В этом перечислении программы Pm и Pn при m n различны, хотя и могут вычислять одну и ту же функцию. При этом существуют алгоритмы A1 и A2 со следующим условием.

• По каждой программе P с помощью алгоритма A1 вычисляется ее кодовый номер n γ P .

•По каждому номеру n N с помощью алгоритма A2 находится программа с номером n.

Алгоритм A1 назовем кодированием программ, а алгоритм A2 — декодированием.

Нумерация множества вычислимых функций. Используя нумерацию программ, получим теперь нумерацию вычислимых функций. Пусть F — множество всех вычислимых функций. Обозначим через Fn множество всех n-арных вычислимых функций.

Зафиксируем число n N и занумеруем функции из Fn, т.е. занумеруем все n-арные вычислимые функции. Пусть дана программа Pa с номером a при нумерации программ. Обозначим n-арную функцию, значение которой вычисляется МНР с программой Pa через φna . Это означает выполнение условий 1) и 2).

1)Если в начале работы регистры равны x1, . . . , xn, 0, . . . , и значение

функции φna x1, . . . , xn существует и равно y, то МНР останавливается и регистре R1 содержится число y.

2)Если φna x1, . . . , xn не определено, то МНР работает бесконечно. Если индекс a в программах Pa пробегает все натуральные числа, то

функции φna пробегают все n-арные вычислимые функции. Имеем следующую нумерацию νn элементов из Fn:

φn,	φn,	φn, . . .	(8.21)
0	1	2

В этой последовательности перечислены все n-арные вычислимые функции. Однако две различные программы могут вычислять одну и ту же функцию. Поэтому возможны повторения φna φnb при a b.

Для множества всех вычислимых функций от одного аргумента имеем нумерацию ν элементов из F1:

φ1,	φ1,	φ1	, . . . .	(8.22)
0	1	2

Если значение n фиксировано на протяжении некоторых рассуждений и ясно из контекста, то опускаем верхний индекс n в φna и записываем φa.

71

Вместо (8.21) получаем запись	без верхних индексов
φ0,	φ1, φ2, . . .	(8.23)

В (8.21) каждого n перечислены все n-арные вычислимые функции. Уберем повторения в перечислении (8.21). Имеем исходную последовательность функций φn0 , φn1 , φn2 , . . . , с повторениями, из которой получим новую последовательность без повторений

φn	,	φn		,	φn	, . . .	(8.24)
α 0		α 1			α 2
Номера α 0 , α 1 , α 2 , . . .			получим			так. Вначале	расположим

функцию φn0 . Поэтому α 0 0. Затем вычеркиваем в исходной после-

довательности все вхождения φn	. Берем в качестве α 1 номер k пер-
α 0
вой невычеркнутой функции. Получим α 1 k. Затем вычеркиваем φn
	α 1

и т.д. Получим последовательность (8.24) без повторений, состоящую из всех n-арных вычислимых функций. Поэтому множество n-арных вычислимых функций счетно. Заметим, что у нас нет никаких оснований считать функцию α x вычислимой функцией.

Рассмотрим отображение θ : F N, заданное следующим правилом. Пусть f — n-арная вычислимая функция, где n 0. Пусть m — номер

места f в последовательности (8.24), т.е. f	φn	. Тогда
	α m
θ f π m, n .		(8.25)

ТЕОРЕМА 8.6 . Отображение θ является биекцией множества F во множество N . В частности, множество всех вычислимых функций счетно.

Доказательство. Инъективность. Пусть f, g F, с числом аргументов n1 и n2 и номерами m1 и m2. Предположим, что f g. Так как f g, то n1 n2 или m1 m2 т.е. m1, n1 m2, n2 . Из инъективности π и (8.25) получаем θ f θ g .

Сюръективность отображения θ непосредственно следует из (8.25) и сюръективности π. Поэтому отображение θ является биекцией.

Теорема доказана.

Рассмотрим теперь нумерацию ν1 областей определения и нумерацию ν2 областей значений n-арных вычислимых функций. Обозначим соответственно через Da и Ea область определения и область значений функции φna . Сопоставив числу a N множество Da получим нумерацию ν1, а сопоставив числу a N множество Ea получим нумерацию ν2.

72

Теорема о параметризации. Пусть f x, y — произвольная вычислимая функция с двумя переменными. Зафиксируем в f x, y переменную x, полагая вначале x 0, затем x 1, и т.д.

Пусть x 0. Получим функцию g y f 0, y от одной переменной. Функция g y является вычислимой функцией, и поэтому присутствует в

последовательности φ0,		φ1, φ2, . . . на некотором месте, которое обо-
значим k 0 . Поэтому g y есть функция φk 0 и f 0, y				φk 0 y для
всех y	N. При x	1 получим функцию φk 1	f 1, y и равенство
f 1, y	φk 1 y и т.д.

Итак, для любого x N можно подобрать номер k x с условием

f x, y φk x y для всех x, y N.

(8.26)

Получили функцию k x из N в N с условием (8.26).

Покажем, что в качестве k x можно подобрать вычислимую функцию.

ТЕОРЕМА 8.7 (о параметризации). Пусть f x, y — вычислимая функция. Существует всюду определенная, вычислимая функция k x с условием, что f x, y φk x y для всех x, y N.

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

Пусть P — программа для вычисления функции f x, y . Допустим, что x a. Функция φk a f a, y является вычислимой функцией, и МНР программа Pk a , вычисляет эту функцию. Укажем алгоритм A получения по числу a программы Pk a . Данную программу Pk a выразим в виде

T 1, 2

Z 1

S 1	(8.27)
. . .
S 1	a раз
P

В регистр R1 перед первым тактом работы данной программы занесено число y, в остальных регистрах находится число 0.

y 0 0 . . .

73

Вначале командой T 1, 2 перенесем число y из R1 в регистр R2. Затем регистр R1 обнулим и a раз добавим единицу. Перед выполнением подпрограммы P имеем следующий вид регистров

a y 0 . . .

При выполнении подпрограммы P в регистр R1 заносится f a, y g a и МНР останавливается. Ясно, что данное правило (8.27) получения по числу a N программы Pk a можно считать алгоритмом.

Теорема доказана.

Канторовская нумерация пар и произвольных строк натуральных чисел. Рассмотрим еще один важный пример однозначной нумерации пар натуральных чисел. Пусть

Ax, y x, y N .

Элементы множества A расположим в следующем порядке

0, 0 , 0, 1 , 1, 0 , 0, 2 , 1, 1 , 2, 0 , 0, 3 , . . .
B0 B1	B2	B3	(8.28)

Пары в данной последовательности выписаны по блокам B0, B1, . . . , так что в каждом блоке Bs помещены пары x, y с заданной суммой s x y. Внутри блока пары упорядочены по возрастанию первой компоненты. Ясно, что каждый элемент из множества A имеет однозначно определенный номер и для произвольного натурального числа существует однозначно определенная пара с данным номером. Укажем формулу для определение номера по заданной паре x, y . Считаем, что в последовательности 8.28 номера членов начинаются с 0.

ТЕОРЕМА 8.8. Обозначим через c x, y номер пары x, y в последовательности 8.28 . Тогда

	c x, y	x y 2 3x y		(8.29)
			.
		2

Доказательство. Рассмотрим пару x, y . Она содержится в блоке Bs, где s x y, состоящем из x y 1 пар и имеющим вид

Bs 0, x y , 1, x y 1 , . . . , x, y , . . . , x y, 0 .

(8.30)

74

До блока Bs расположены блоки B0, B1, . . . Bx y 1. В них соответственно 1, 2, . . . , x y пар. Поэтому перед блоком Bs находится

	x y 1 x y
1 2 x y
	2
пар. В самом блоке Bs	перед парой x, y находится x пар 0, x y ,
1, x y 1 , . . . , x	1, y 1 . Номера пар в (8.28) начинаются с ну-

ля. Поэтому номер пары равен числу предшествующих пар. Тогда номер пары x, y равен

	x y 1 x y		x y 2 3x y
		x	.
	2
			2

Теорема доказана.

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

c2 x1, x2	c x1, x2 ,
c3 x1, x2, x3	c2 c x1, x2 , x3 c c x1, x2 , x3 ,
c4 x1, x2, x3, x4	c3 c x1, x2 , x3, x4 c c c x1, x2 , x3 , x4 ,
	. . .

Если нужно найти номер тройки x1, x2, x3 , то вначале находим номер n пары x1, x2 , а затем номер пары n, x3 . То же для четверок и т.д.

75

Упражнения к лекции 8

ЗАДАЧА 1. Найти номера пар 1, 1 , 0, 4 , 4, 0 , 2, 3 при нумерации π, заданной равенством (8.3).

ЗАДАЧА 2. Найти пары, имеющие номера 3, 19, 15, 0 при нумерации π.

ЗАДАЧА 3. Найти номера троек 1, 1, 1 , 2, 1, 1 , 1, 1, 3 при нумерации ζ, заданной равенством (8.10).

ЗАДАЧА 4. Найти тройки, имеющие номера 15, 0, 2 при нумерации ζ.

ЗАДАЧА 5. Найти номер последовательности 1, 0, 2, 3 при нумерации τ , заданной равенством (8.15).

ЗАДАЧА 6. Найти последовательность, имеющую номер 15 при нумерации τ .

ЗАДАЧА 7. Найти номера пар 1, 1 , 1, 1 , 2, 3 при нумерации Кантора из (8.28) и (8.29).

ЗАДАЧА 8. От нумерации Кантора пар натуральных чисел можно перейти к нумерации троек, четверок и произвольных n-ок на-

туральных чисел. Для нумерации троек чисел в лекции 8 указана функция c3 x1, x2, x3 , заданная правилом

c3 x1, x2, x3 c c x1, x2 , x3 .

Найти номера троек 0, 0, 0 , 1, 1, 1 , 2, 3, 1 .

ЗАДАЧА 9. Доказать, что множество всех функций f x из N в N несчетно.

ЗАДАЧА 10. Доказать, что множество всех вычислимых функций f x из N в N счетно.

76

Лекция 9. Универсальные функции

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

Предположим, что мы имеем некоторую функцию U t, x от двух переменных. Будем конструировать с помощью U t, x новые функции fa от одной переменной. Для этого фиксируем первый аргумент в функции U t, x . Пусть a N . Считаем, что t a постоянно в функции U t, x . Получим функцию fa от одной переменной x, которая задается правилом

fa x U a, x для всех x N.

(9.1)

ОПРЕДЕЛЕНИЕ 9.1 . Функция U t, x от двух переменных является универсальной функцией для класса вычислимых функций от одной переменной, если выполнены следующие два условия.

1 Для каждого a N функция

fa x U a, x

(9.2)

является вычислимой функцией.

2 Произвольная вычислимая функция от одной переменной является функцией fa x для некоторого a N.

Функция fa x U a, x называется сечением функции U при t a. Так как функция U t, x частичная функция, то и ее сечения в общем случае также частичные функции. Поскольку все вычислимые функции от одной переменной получаются из универсальной функции U t, x в виде сечений, то можно сказать, что функция U их «порождает».

Обобщим определение (9.1) на случай частичных функций от n переменных. В этом случае фиксируем значение переменной t a в функции U t, x1, . . . , xn от n 1 переменной. Получаем некоторую функцию fa x1, . . . , xn от n переменных, заданную правилом

fa x1, . . . , xn U a, x1, . . . , xn .

(9.3)

77

ОПРЕДЕЛЕНИЕ 9.2. Функция U t, x1, . . . , xn от n 1 переменной называется универсальной функцией для класса вычислимых функций от n переменных, если выполнены следующие два условия.

1 Для каждого a N функция

fa x1, . . . , xn U a, x1, . . . , xn

(9.4)

является вычислимой функцией.

2 Произвольная вычислимая функция от n переменных является функцией fa x1, . . . , xn для некоторого a N.

Следующая теорема является одним из основных результатов теории вычислимых функций.

ТЕОРЕМА 9.1. Существует вычислимая функция U t, x1, . . . , xn от n 1 переменной, являющаяся универсальной функцией для класса всех вычислимых функций от n переменных.

Доказательство. Нам нужно построить универсальную функцию. Вначале мы зададим некоторую функцию U t, x1, . . . , xn , а затем проверим ее универсальность и вычислимость. Для задания функции используем нумерацию φn0 , φn1 , φn2 , . . . всех n-арных вычислимых функций из равенства (8.21) предыдущей лекции. Поскольку у нас число n фиксировано, то опускаем в обозначении функций верхний индекс n. Получаем бесконечную последовательность

φ0, φ1, φ2, . . .

(9.5)

В этой последовательности перечислены с повторениями все n-арные вычислимые функции. Нижний индекс t является номером функции φt. Введем функцию U от n 1 переменной, указав следующее правило для вычисления ее значений:

U t, x1, . . . , xn φt x1, . . . , xn для всех t, x1, . . . , xn N.

(9.6)

Тем самым, чтобы вычислить значение функции U от n 1 переменной t, x1, . . . , xn, нужно взять в (9.5) n-арную функцию φt с номером t и вычислить ее значение от набора переменных x1, . . . , xn .

Проверим универсальность функции U , используя определение универсальности (9.2), состоящее из двух пунктов 1) и 2).

78

1) Пусть t a. По (9.6) получим некоторую n-арную функцию

φa x1, . . . , xn , которая вычислима.

2) Если параметр t пробегает все числа из N, то и функции φt x1, . . . , xn пробегают все функции из (9.5).

Осталось выполнить самое трудное — проверить вычислимость заданной в (9.6) функции U . Эту проверку выполним в несколько шагов.

Шаг 1, изображение процесса вычислений. В лекции 8 мы занумеровали все программы и получили последовательность программ МНР

P0, P1, P2, . . . (9.7)

Затем мы обозначили через Mi машину с программой Pi и получили последовательность всех МНР

M0, M1, M2, . . . (9.8)

Эти МНР вычисляют соответственно функции φ0, φ1, φ2, . . . из (9.5). Перед началом вычислений расположим машины из (9.8) в первую строку некоторой таблицы. Машины готовы стартовать. У каждой из них в регистрах набор аргументов x1, . . . , xn . Машины намерены выполнить команду с номером j 1.

После старта все машины совершат один такт работы, изменят содержимое регистров и снова намерены выполнить команду с некоторым очередным номером j (индивидуальным для каждой машины). Изобразим эти машины с новыми состояниями во второй строке таблицы. После второго такта получим третью строку и т.д.

Тем самым время течет дискретно по тактам: такт 1, такт 2, . . . В каждый очередной такт времени срабатывает такт работы каждой машины. Возможно, что некоторые машины уже остановились, а другие продолжают работу. Если машина остановилась после такта m, то считаем, что при последующих тактах m 1, m 2, . . . с ее регистрами не происходит никаких изменений и номер очередной команды j, которую она должна исполнить, равен 0. Тем самым все машины, и те, которые работают бесконечно, и те, которые останавливаются, участвуют в каждом такте «течения времени». Однако при этом машины разделены на два типа: 1) машины, работающие бесконечно и 2) машины, которые останавливаются после некоторого такта m. Признак машины типа 2) следующий.

Машина Mt имеет тип 2) тогда и только тогда, когда существует номер ее очередной команды j, равный 0.

79

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

	M00	M10	M20	M30 . . .
	M01	M11	M21	M31 . . .	(9.9)
	M02	M12	M22	M32 . . .

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

Через Mtm изображена машина Mt, совершившая m тактов работы. Каждый столбец отражает ход вычислений конкретной машины Mt.

Шаг 2, кодирование вычислений. Пусть машина Mt, совершила m 0 тактов работы. Введем понятие «состояние машины» после m-го такта работы. Для этого вначале определим понятие «конфигурация регистров». Совершив m тактов работы, машина имеет некоторое содержимое регистров, которое является бесконечной последовательностью r1, . . . , rk, 0, . . . натуральных чисел, где лишь конечное число членов не равно 0. Назовем эту последовательность конфигурацией регистров и обозначим через r. Имеем

r r1, . . . , rk, 0, . . . — конфигурация регистров.

(9.10)

Для следующего m 1 такта работы машины имеется j — номер команды, которую она должна исполнить в этом такте. Назовем текущим состоянием или просто состоянием машины набор из конфигурации регистров и номера очередной команды. Обозначим конфигурацию регистров через

r r1, . . . , rk, 0, . . . , а номер очередной команды — через j. Получим изображение состояния машины в виде пары

q r, j — состояние машины.

(9.11)

Ясно, что пара r, j однозначно задает следующий такт работы машины. При этом клетки таблицы (9.9) отражают текущие моменты — состояния машин.

Наша дальнейшая задача — закодировать состояния машин. При кодировании объектов произвольному объекту a сопоставляем его код — натуральное число, которое обычно обозначаем через a .

Кодирование конфигурации регистров. Пусть задана конфигурация регистров r r1, . . . , rk, 0, . . . некоторой машины Mt.

80