11.7. Вычислимость с оракулом

Определение класса частично рекурсивных функций легко модифицировать для случая вычислимости с ораку­лом. Пусть имеется некоторая всюду определённая функ­ция а. Рассмотрим класс ^*[а], который состоит из ба­зисных функций, функции а и всех других функций, ко­торые могут быть из них получены с помощью подста­новки, примитивной рекурсии и минимизации.

(Формально можно сказать так: J~\ci\ есть минималь­ный класс, который содержит базисные функции, функ­цию а и замкнут относительно подстановки, примитив­ной рекурсии и минимизации. Такой минимальный класс существует — достаточно взять пересечение всех клас­сов с этими свойствами.)

Теорема 80. Класс J~\ci\ состоит из всех функций, вы­числимых с оракулом а (то есть с помощью программ, вызывающих а как внешнюю процедуру).

<] Прежде всего заметим, что все функции из клас­са J~\ci\ вычислимы с помощью таких программ. Это можно объяснить, например, так. Программы с конеч­ным числом переменных вычисляли все частично-рекур­сивные функции. Если добавить к ним примитивную операцию вычисления значения функции а в заданнойточке, то они точно так же будут вычислять все функ­ции из класса Т\а\.

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

Для этого вспомним критерий относительной вычи­слимости, данный нами выше в разделе 7.2 (теорема 45). Пусть функция / вычислима относительно всюду опре­делённой функции а. Тогда, как мы знаем, существует перечислимое множество IV троек вида (х, у, 2), где х ту — натуральные числа, а 2 — образцы (функции с конечной областью определения), которое является кор­ректным (тройки с одинаковым х, но разными у содер­жат несовместные образцы) и для которого

f(x) = г/ <=> 32 ((ш, г/, 2) 6     и 2 есть часть функции а).

Мы сейчас покажем, что свойство «2 есть часть функ­ции а» является примитивно рекурсивным относитель­но а: его характеристическая функция получается из ба­зисных функций и из а с помощью операций подстановки и рекурсии. (Напомним, что мы отождествляем образцы с их номерами в какой-то нумерации; о её выборе см. ни­же.)

После этого останется записать IV как проекцию примитивно рекурсивного множества ((ш,г/, 2) £ № ^ -<=> Зи (г>(х, у, 2, и) = 0), где V примитивно рекурсивна), и заметить, что

f(x) = р\ (рг V1 {х, г) = 0).

•Здесь V1 — примитивно рекурсивная относительно а функция, для которой 1>'{х, [у, 2, и]) = 0 тогда и только тогда, когда 1>{х, у, 2, и) = 0 и 2 есть часть функции а, а функция р\ выделяет из номера тройки [г/, 2, и] её первый член у.

Осталось показать, что множество {2 | образец с но­мером 2 есть часть функции а} является примитивно ре­курсивным относительно а. При доказательстве мы бу­дем предполагать, что нумерация образцов такова, что следующие функции примитивно рекурсивны (они опре­делены для образцов с непустой областью определения; для пустого образца доопределим их как угодно):

• 1ай^х(<) — наибольшее из чисел, на котором опре­делён образец с номером 2;

• 1ав!-у(2) — значение функции-образца с номером 2 в максимальной точке своей области определения;

• аН-ЬиНая^) — номер образца, который получится из образца с номером I, если удалить максимальную точку области определения.

Тогда можно записать такое рекурсивное определе­ние: образец с номером t есть часть функции а, если либо этот образец пуст, либо а(1а81-х(2)) = 1а81-у(2) и образец с номером аН-ЬиНая^) есть часть функции а.

Это определение использует «возвратную рекурсию», которая разобрана в теореме 74 (с. 151); значение функ­ции определяется рекурсивно через её значения в мень­ших точках. Надо только выбрать нумерацию образ­цов так, чтобы аН-ЬиНая^) было меньше 2 для всех I. Этого несложно добиться: например, можно нумеровать образцы с помощью простых чисел, считая, что обра­зец {(а, Ь),..., (е, /)} имеет номер р^+1К . ,р^+1\ где р{ — простое число с номером г (так что ро = 2, р\ = 3, р2 = 5,. . .). >

Заметим, что доказательство стало бы немного про­ще, если использовать только «сплошные образцы» (обла­стью определения которых является некоторый началь­ный отрезок натурального ряда) — тогда можно начать с того, что установить примитивную рекурсивность (от­носительно а) функции п I—У [а(0),а(1),.. .,а(п)]. Легко понять также, что в определении относительной вычи­слимости можно ограничиться только сплошными образ­цами.