§ 12.10. Явная форма общерекурсивных функций

В § 12.8 мы ввели понятие ограниченного оператора наименьшего числа, который ставит в соответствие примитивно-рекурсивному предикату (или примитивно-рекурсивной функции ), представляющей предикат ) примитивно-рекурсивную функцню следующим образом:

(12.23)

при условии

или.

где z в общем случае может быть примитивно-рекурсивной функцией :

Рассмотрим теперь случай, когда ограничение оператора снято.

Пусть - рекурсивная функция такая, что

(12.24)

Здесь уже не указана верхняя граница для у, а говорится лишь, что для всех существует такой у, что

В этом случае функция , определенная с помощью применения оператора наименьшего числа

(12.25)

оказывается заведомо вычислимой.

Действительно, для вычисления ее значения в любой точке достаточно последовательно вычислять

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

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

Оказалось, что в этом случае можно построить систему равенств Е, которая бы рекурсивно определяла функцию , т. е. функция оказывается общерекурсивной.

Чтобы упростить выкладки, рассмотрим функцию одного переменного

(12.26)

Система Е, рекурсивно определяющая , в этом случае будет такова:

Покажем, что Е рекурсивно определяет . Пусть — некоторое число, и мы хотим определить . Согласно 3, Е (равенству 3 системы Е)

Дальше возможны два случая. Либо , и тогда можно применить лишь первое определяющее равенство

Но нуль в этом случае и должен быть значением функции согласно (12.26).

Если же , то ее значение можно представить как и воспользоваться вторым определяющим равенством

Теперь опять возможно два случая. , и тогда можно пользоваться лишь равенством 1, Е

и, следовательно, . Но в этом случае 1,? и должно давать значение функции согласно (12.26). Если же то ее представляем в виде и опять пользуемся равенством 2, Е:

и так до тех пор, пока впервые не встретится такое, что . Это и будет значением .

Таким образом, система Е действительно рекурсивно определяет функцию

и, следовательно, является общерекурсивной функцией.

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

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

Любая общерекурсивная функция может быть представлена в виде

(12.27)

где — примитивно-рекурсивные функции, причем для функции справедливо утверждение

Форма (12.27) носит название явной формы общерекурсивных функций. Приведем идею - доказательства этого утверждения. Пусть имеется система равенств , ей рекурсивно определяющая функцию . Каждому равенству соответствует его гёделевский номер . За гёделевский номер всей системы Е тогда следует принять число

Будем теперь как-либо выводить из системы Е новые равенства. Это значит, что мы будем последовательно получать равенства

(12.28)

Если — гёделевский номер равенства , то каждому выводу (т. е. каждой цепочке вида ) можно поставить в соответствие гёделевский номер вывода

Пусть мы интересуемся значением функции в точке т. е. мы хотим вывести из системы Е равенство вида

(12.29)

Какими свойствами должен обладать гёделевский номер z этого вывода?

1. Переход от одних равенств к другим, как мы знаем, может совершаться с помощью подстановки чисел на место переменных и замены вхождений. При этом гёделевские номера новых равенств оказываются примитивно-рекурсивными функциями гёделевских номеров исходных равенств, так как операции замены вхождения, подстановки, определения гёделевского номера связаны лишь с примитивно-рекурсивными функциями.

Некоторые из этих функций рассмотрены нами выше — это функции вида

и некоторые другие.

Поэтому первое свойство, которому должно удовлетворять число z, таково: любой из показателей . разложения числа z на простые множители есть либо гёделевский номер одного из определяющих равенств ей либо он представляет собой значение определенной примитивно-рекурсивной функции от этих номеров.

2) Последний показатель разложения числа одолжен быть гёделевским номером равенства вида (12.29). В итоге оказывается, что предикат

является примитивно-рекурсивным предикатом. Следовательно, его представляющая функция также примитивно-рекурсивна, и она равна нулю лишь для тех и только тех , которые являются гёделевскими номерами выводов, заканчивающихся равенством

Поэтому задача нахождения нужного вывода может быть теперь сформулирована так: найти хоть одно число такое, чтобы

(12.30)

Так как вывод в любой точке существует (Е по условию рекурсивно определяет , то функция обладает свойством

(12.31)

Найдя такое , для которого выполняется (12.30), мы можем расшифровать этот гёделевский номер и получить

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

Если, как мы установили, любое , для которого

есть гёделевский номер искомого вывода, то и

есть также гёделевский номер вывода. Поэтому окончательно получим

и — примитивно-рекурсивные функции и для выполняется условие (12.31).

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

Однако, в отличие от примитивно-рекурсивных функций, множество общерекурсивных функций не является эффективно-счетным (подробнее см. в § 12.12) и, следовательно, невозможно методом Петер построить пример вычислимой функции более общей, чем общерекурсивная.

В заключение этого параграфа выпишем схемы, определяющие общерекурсивные функции. Здесь схемы I—V — уже знакомые нам схемы определения примитивно-рекурсивных функций, а схема VI представляет собой явную форму общерекурсивной функции:

причем

Теперь можно дать такое определение общерекурсивной функции. Функция называется общерекурсивной, если она может быть определена с помощью конечного числа применений схем I — VI.

Отметим еще, что так как схемы I—V, определяющие примитивно-рекурсивные функции, являются частью схем I—VI, определяющих общерекурсивные функции, примитивно-рекурсивные функции являются частным случаем общерекурсивных функций; всякая примитивнорекурсивная функция есть общерекурсичная функция, но не наоборот.