§ 12.8. Пример построения вычислимой, но не примитивно-рекурсивной функции
Выше был описан класс примитивно-рекурсивных функций. Как было видно из самого построения, каждая примитивно-рекурсивная функция вычислима.
Верно ли обратное утверждение? Всякая ли вычислимая функция примитивно-рекурсивна?
Отрицательный ответ на эти вопросы был дан почти одновременно Петер и Аккерманом, которые, идя совершенно различными путями, построили примеры вычислимой, но не примитивно-рекурсивной функции.
Познакомимся с идеей примера Петер.
Р. Петер впервые обратила внимание на то, что множество примитивно-рекурсивных функций является счетным множеством.
Действительно, класс первоначальных функций счетен (так как число различных переменных 
и констант q счетно). Следовательно, счетен класс примитивно-рекурсивных функций, определенных с помощью одного применения схем IV или V, потому что счетно множество наборов 
для схемы IV или пар 
Для схемы V, образованных из элементов счетного класса.
Далее, счетно множество примитивно-рекурсивных функций, образованных с помощью двух применений схем IV или V и т. д. Поэтому и вообще счетно множество примитивно-рекурсивных функций. В частности, счетно множество примитивно-рекурсивных функций одной переменной (как часть всего счетного множества).
Петер удалось все примитивно-рекурсивные функции одной переменной эффективно перенумеровать, т. е. расположить их в последовательность
(12.14)
так, что по виду функции можно определить ее номер и по номеру определить вид той функции, которая этим номером обладает. Коль скоро удалось эффективно перенумеровать все примитивно-рекурсивные функции одной переменной, немедленно оказалось возможным построить пример вычислимой, но не примитивно-рекурсивной функции.
Введем функцию 
функция 
вычислима (так как по значению 
можно отыскать соответствующую функцию 
) и вычислить ее значение при заданном 
тем самым будет вычислено значение 
. Но она не примитивно-рекурсивна. Действительно, если бы 
была примитивно-рекурсивна, то была бы примитивно-рекурсивна и функция 
как функция одной переменной. Тогда была бы примитивно-рекурсивна и функция 
так как прибавление единицы есть допустимая операция «следования за».
Но так как в ряду (12.14) содержатся все примитивно-рекурсивные функции одной переменной, то нашелся бы такой номер 
, что
для всех 
. Иначе
Так как это равенство должно выполняться для всех 
, то, в частности, оно должно выполняться и для 
. Но тогда
что невозможно. Значит, перечисляющая функция 
не примитивно-рекурсивна. Вместе с тем она заведомо вычислима. Следовательно, класс примитивно-рекурсивных функций не охватывает всех вычислимых функций и нуждается в расширении.
Если в классе элементарных функций ограничение состояло в том, что с помощью допустимых операций невозможно было строить очень быстро растущие функции, то теперь в классе примитивно-рекурсивных функций нас ограничивает принятая форма индукции. Вся беда в том, что мы заранее фиксировали ту схему (схема V), в которой должна проявиться индукция.
Расширение класса примитивно-рекурсивных функций было предложено Гёделем в 1934 г. и основано на одной смелой идее Эрбрана.
