Наше доказательство теорем 76 и 77 позволяет также получить такое следствие, называемое иногда теоремой Клини о нормальной форме:

Теорема 78. Всякая частично рекурсивная функция f представима в виде

\[ f(x)=a(\mu z (b(x,z)=0)), \]

где a и b некоторые примитивно рекурсивные функции.

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

Мы сформулировали эту теорему для случая одноместной функции f, но аналогичное утверждение верно и для функций нескольких аргументов (и доказательство почти не меняется).

  89. Покажите, что одним \[ \mu \] -оператором, применяя его последним, не обойтись: не всякая частично рекурсивная функция представима в виде

\[ f(x)=\mu z (b(x,z)=0) \]

где b некоторая примитивно рекурсивная функция.

Из теоремы Клини о нормальной форме вытекает такое утверждение:

Теорема 79. Всякое перечислимое множество есть проекция примитивно рекурсивного множества.

Перечислимое множество есть область определения рекурсивной функции; представив ее в нормальной форме, видим, что область определения есть проекция множества \[ \{\langle x,z\rangle \mid b(x,z)\hm=0\} \] .

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

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

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

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

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

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

Для этого вспомним критерий относительной вычислимости (теорема 45). Пусть функция f вычислима относительно всюду определенной функции \[ \alpha. \] Тогда, как мы знаем, существует перечислимое множество W троек вида \[ \langle x,y,t\rangle \] , где x и y натуральные числа, а t образцы (функции с конечной областью определения), которое является корректным (тройки с одинаковым x, но разными y содержат несовместные образцы) и для которого

\[ f(x)=y \Leftrightarrow \exists t\; (\langle x,y,t\rangle \in W \text{ и $t$~есть часть функции~$\alpha$}). \]

Мы сейчас покажем, что свойство " t есть часть функции \[ \alpha \] " является примитивно рекурсивным относительно \[ \alpha: \] его характеристическая функция получается из базисных функций и из \[ \alpha \] с помощью операций подстановки и рекурсии. (Напомним, что мы отождествляем образцы с их номерами в какой-то нумерации; о ее выборе см. ниже.)

После этого останется записать W как проекцию примитивно рекурсивного множества ( \[ \langle x,y,t\rangle \hm\in W \hm\Leftrightarrow {\exists u\: (v(x,y,t,u)=0)} \] , где v примитивно рекурсивна), и заметить, что

\[ f(x)=p_{1}(\mu z v'(x,z)=0). \]

Здесь v' примитивно рекурсивная относительно \[ \alpha \] функция, для которой v'(x,[y,t,u])=0 тогда и только тогда, когда v(x,y,t,u)=0 и t есть часть функции \[ \alpha, \] а функция p₁ выделяет из номера тройки [y,t,u] ее первый член y.

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

• last-x(t) наибольшее из чисел, на котором определен образец с номером t ;
• last-y(t) значение функции-образца с номером t в максимальной точке своей области определения;
• all-but-last(t) номер образца, который получится из образца с номером t, если удалить максимальную точку области определения.

Тогда можно записать такое рекурсивное определение: образец с номером t есть часть функции \[ \alpha, \] если либо этот образец пуст, либо \[ \alpha (last-x(t))= last-y(t) \] и образец с номером all-but-last(t) есть часть функции \[ \alpha. \]

Это определение использует " возвратную рекурсию", которая разобрана в теореме 74; значение функции определяется рекурсивно через ее значения в меньших точках. Надо только выбрать нумерацию образцов так, чтобы all-but-last(t) было меньше t для всех t. Этого несложно добиться: например, можно нумеровать образцы с помощью простых чисел, считая, что образец \[ \{\langle a,b \rangle,\dots,\langle e,f\rangle\} \] имеет номер p_a^(b+1)... p_e^(f+1), где p_i простое число с номером i (так что p₀=2, p₁=3, p₂=5, ...).

Заметим, что доказательство стало бы немного проще, если использовать только " сплошные образцы" (областью определения которых является некоторый начальный отрезок натурального ряда) тогда можно начать с того, что установить примитивную рекурсивность (относительно \[ \alpha \] ) функции n \[ \mapsto \] \[ [\alpha (0),\alpha (1),\dots ,\alpha (n)] \] . Легко понять также, что в определении относительной вычислимости можно ограничиться только сплошными образцами.