A08DPPMAT_UPS2006D00

J 1, ρ n 2, q эти числа сравнивается с неизменяемым нулем в реги-

стре Rρ n 2.

Поэтому в общем случае проверяется равенство g x1, . . . , xn, k 0, и

вэтот момент в регистре Rρ n 1 находится число k.

4)Если при проверке командой J 1, ρ n 2, q равенства

g x1, . . . , xn, k 0 получили «да», то из регистра Rρ n 1 командой Iq T ρ n 1, 1 пересылаем найденное число k в R1 и останавливаемся.

Если проверка равенства g x1, . . . , xn, k 0 дает «нет», то наращиваем командой S ρ n 1 число k в регистре Rρ n 1 на единицу и переходим к следующей проверке g x1, . . . , xn, k 1 0. В итоге получим искомое число k, или МНР работает бесконечно. Тогда f x1, . . . , xn не существует.

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

Как следствие трех полученных выше теорем имеем.

ТЕОРЕМА 7.4. Всякая частично рекурсивная функция вычислима на некоторой МНР.

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

ТЕОРЕМА 7.5. Функция f является вычислимой функцией тогда и только тогда, когда функция f вычислима на некоторой МНР.

Подробное изложение теории алгоритмов на основе понятия машины с неограниченными регистрами можно найти в [13]. Мы будем использовать МНР для нумерации программ и вычислимых функций, а также для построения универсальной функции.

61

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

В следующих задачах используется общий вид программ (7.2), (7.4) и (7.5) для реализации на МНР операторов суперпозиции, примитивной рекурсии и минимизации.

ЗАДАЧА 1. Выразить функцию умножения f x, y x y с помощью оператора примитивной рекурсии через нулевую функцию g и функцию h. Используя общий вид программы (7.4), составить программу для МНР, вычисляющую функцию f x, y .

ЗАДАЧА 2. Рассмотрим функцию f x x! 1 2 . . . x. При этом 0! 1. Составить программу для вычисления функции f x .

Указание. Имеем

0! 1

f x 1 x 1 ! x 1 x! x 1 f x h x, f x

для функции h x, y x 1 y. Поэтому функция f x получена с помощью оператора примитивной рекурсии из нульарной функции g, совпадающей с числом 1, и бинарной функции h x, y x 1 y.

Используя общий вид программы (7.4), составить программу для МНР, вычисляющую функцию f x .

ЗАДАЧА 3. Составить программу для МНР, вычисляющую функцию f x, y xy . При этом 00 1.

ЗАДАЧА 4. Составить программу для МНР, вычисляющую функцию

1, если x 0,

0, если x 0.

ЗАДАЧА 5. Составить программу для МНР, вычисляющую функцию f x 2x.

ЗАДАЧА 6. Составить программу для МНР, вычисляющую функцию f x, y, z x y z.

ЗАДАЧА 7. Составить программу для МНР, вычисляющую функцию f x, y xy 3.

62

ЗАДАЧА 8. Составить программу для МНР, вычисляющую функцию f x x2.

ЗАДАЧА 9. Составить программу для МНР, вычисляющую функцию

y, если x y,

0, если x y.

ЗАДАЧА 10. Составить программу для МНР, вычисляющую функцию f x, y x y .

63

Лекция 8. Нумерации

Теория нумераций — раздел теории алгоритмов, в котором изучаются свойства классов объектов, занумерованных с помощью натуральных чисел. Присвоив номера объектам (машинам Тьюринга, МНР, частично рекурсивным функциям и т.д. ), мы можем во многих случаях получить глубокие результаты об этих объектах. Идея использования нумерации объектов для получения различных утверждений об этих объектах принадлежит К. Геделю.

В данной лекции мы осуществим нумерацию программ МНР и нумерацию множества вычислимых функций. С помощью этих нумераций в лекции 9 будут построены универсальные функции.

Пусть A — произвольное непустое конечное или счетное множество.

ОПРЕДЕЛЕНИЕ 8.1. Нумерацией множества A называется произвольное сюръективное отображение ν множества натуральных чисел N во множество A.

При этом пара A, ν называется нумерованным множеством. Вместо слов «сюръективное отображение» можно говорить «отображение на». Если отображение ν инъективно (и поэтому биективно), то нумерация ν называется однозначной нумерацией. Пусть

нумерация множества A. Если ν n a, то натуральное число n называется номером элемента a при нумерации ν. Элемент a A может иметь несколько номеров, поскольку отображение ν не обязательно инъективно. Обозначим элемент a с номером n через an. Тогда элементы нумерованного множества A можно представить в виде последовательности

a0, a1, a2, . . . (8.2)

В общем случае в этой последовательности возможны повторения, т.е. равенства ai aj при i j. Особый интерес представляют однозначные нумерации, где таких повторений нет.

Пусть дана однозначная нумерация ν : N A. Множество A является счетным множеством. В теории алгоритмом на отображение ν будем накладывать дополнительные ограничения.

64

ОПРЕДЕЛЕНИЕ 8.2 . Пусть A — множество, состоящее из конструктивных объектов. Множество A называется эффективно счетным множеством, если существует однозначная нумерация ν : N A такая,что выполнены следующее два условия.

1 Существует алгоритм A1, вычисляющий по элементу a A его номер ν a N.

2 Существует алгоритм A2, устанавливающий по номеру n N элемент a A с данным номером.

Нумерация ν называется в этом случае геделевской нумерацией. Условия 1) и 2) можем выразить в следующем виде.

Функции ν : N A и ν 1 : A N вычислимы.

Используя вместо самих объектов их номера при некоторой нумерации, мы сводим рассуждений об этих объектах к рассуждениям о натуральных числах. Пусть A — произвольный алгоритм, перерабатывающий объекты из множества X в объекты множества Y . Пусть ν1 и ν2— геделевские нумерации множеств X и Y , изображенные на следующем рисунке.

XA Y

N f N

Рассмотрим данный набор правил A как процедуру вычисления некоторой функции f : N N. Пусть на входе алгоритма A имеется объект P X, который перерабатывается в объект Q Y . Заменим объекты P и Q на их номера n и m при нумерациях ν1 и ν2. Сопоставляя числу n число m, получаем функцию f : N N. Из того, что A алгоритм нетрудно получить вычислимость функции f . Действительно, взяв число n, некоторыми инструкциями найдем объект P с данным номером. Затем алгоритмом A найдем Q A P и вычислим номер m объекта Q. При этом f n m. Получили алгоритм для вычисления функции f .

Рассмотрим примеры геделевских нумерацией и эффективно счетных множеств.

ТЕОРЕМА 8.1 . Множество N N является эффективно счетным.

Доказательство. Рассмотрим отображение π : N N N, заданное следующим правилом:

65

Проверим биективность отображения π, и укажем алгоритмы вычис-

б) Сюръективность. По элементу a A найдем пару m, n с условием

Итак, мы проверили биективность π и одновременно указали способ для вычисления π 1 a . В формулах (8.3), (8.7) и (8.8) указаны способы для вычисления функций π, π1, π2. Из этих формул следует вычислимость данных функций. При этом мы ссылаемся на тезис Черча и не производим непосредственную проверку рекурсивности функций π, π1, π2. Поскольку функции π и π 1 вычислимы, то множество N N является эффективно счетным.

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

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

66

ТЕОРЕМА 8.2. Множество N N N является эффективно счетным.

Применим определение ζ из (8.10) к равенству (8.12), где помечены

Оно верно по (8.5).

Из выражений (8.10) и (8.11) для функций ζ и ζ 1 следует их вычислимость. Поэтому множество N N N является эффективно счетным.

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

ТЕОРЕМА 8.3 . Множество A, состоящее из всевозможных конечных последовательностей натуральных чисел, является эффективно счетным.

Доказательство. Имеем

67

Зададим отображение τ : A N по следующему правилу: если

aa1, a2, . . . , ak A, то

запись означает, что число τ a записано в двоичной системе счисления

2a1 2a1 a2 1 2a1 a2 a3 2 2a1 b2 ak k 1

2b1 2b1 b2 1 2b1 b2 b3 2 2b1 b2 bl l 1 . (8.16)

Проверим вначале, что a1 b1. Допустим a1 b1. Тогда левая часть в (8.16) делится на 2b1 1, а правая часть не делится, противоречие. Разделим (8.16) на 2a1 2b1 , и затем аналогично получим a2 b2 и т.д. Имеем

ab, что и нужно.

Итак, τ сюръективно и поэтому биективно. Вычислимость функций τ и τ 1 следует из равенств (8.15) и (8.17).

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

ТЕОРЕМА 8.4 . Множество всех команд МНР является эффективно счетным.

Доказательство. Обозначим через K множество всех команд МНР. Элементы из K, т.е команды МНР, имеют один из следующих четырех видов: Z n , S n , T m, n , J m, n, q , где m, n N .

68

Разобьем множество K на подмножества K1, K2, K3, K4 следующим способом:

Зададим отображение β : K N правилом

Проверим биективность отображения β.

а) Инъективность. Пусть a, b K и a b. Проверим, что β a β b . Если a Ki и b Kj , где i j, то числа β a и β b имеют разные остатки при делении на 4. Поэтому β a β b . Пусть a, b содержатся в одном и том же множестве Ki. Допустим i 1, т.е. a Z n1 , b Z n2 . Так как a b, то n1 n2. Поэтому, β a β b . Аналогично рассматриваются случаи i 2, 3, 4. Итак, β инъективно.

б) Сюръективность. Пусть l N. Найдем a K с условием β a l. Если l имеет остаток 0 при делении на 4, то l 4q, где q 0. Тогда

для искомого прообраза a имеем a Z q 1 , где q 1 1. Аналогично находим a, если l имеет остаток 1,2 или 3 при делении на 4. Итак, β сюръективно. С учетом а) отображение β биективно.

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

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

ТЕОРЕМА 8.5. Множество P, состоящее из всевозможных программ МНР, является эффективно счетным.

69

Образ γ P N элемента P P вычисляем по правилу

где функции τ и β введены в теоремах 8.3 и 8.4. По этому правилу вначале для последовательности команд I1, . . . , Is, используя функцию β, вычисляем строку чисел β I1 , . . . , β Is . Затем по этой строке, используя функцию τ , находим номер программы γ P . При этом все перечисленные действия образуют некоторый алгоритм, т.е. функция γ вычислима. Проверим биективность отображения γ.

а) Инъективность. Пусть γ P1 γ P2 . Покажем, что P1 P2. Равенство программ понимаем как равенство последовательностей

Из инъективности β получаем P1 P2, что нужно.

а) Сюръективность. Пусть l N. Найдем P P с условием γ P l. Вначале используем сюръективность τ и по числу l N находим строку

a1, . . . , ak с условием τ a1, . . . , ak l. Затем, используя сюръективность β, для каждой компоненты ar N находим команду МНР Ir с усло-

вием β Ir ar. В итоге получим искомую программу I1, I2, . . . , Ik. Итак, γ сюръективно и поэтому биективно. При этом функции γ и γ 1 вычислимы.

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

Биекция γ, задаваемая правилом (8.19), существенным образом используется в дальнейших рассуждениях. Программу P с номером

nγ P будем обозначать через Pn.

ОПРЕДЕЛЕНИЕ 8.3. Номер n γ P называется кодовым (геделевым) номером программы P .

Для множества P, состоящего из всех МНР программ, имеем перечисление

70