A08DPPMAT_UPS2006D00
.pdfВ этом перечислении программы 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