§ 12.9. Общерекурсивные функции. Определение

Эрбрана — Гёделя

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

Пример 1. Пусть задана система равенств

Просмотрим цепочку формальных выкладок, позволяющих из системы (12.15) — (12.18) вычислить .

В (12.18) подставим

(12.19)

2) В (12.19) вместо подставим 4 согласно (12.17):

(12.20)

3) Воспользуемся (12.15):

Поступая далее аналогично, последовательно получаем:

4) .

5) .

6) .

Пример 2. Пусть задана некоторая функция Ф с помощью схемы

(12.21)

и пусть нас интересует значение . Попробуем формально проанализировать, какие операции нам нужно совершить, чтобы, пользуясь схемой (12.21), , вычислить :

1) Подставим в (12.22) вместо переменных числа . Имеем

2) Подставим в и определим :

3) Аналогично

4) Подставим в (12.21) . Имеем

5) Заменим в (3) (0,5) на 5, согласно (4),

6) Подставляя из (5) в (2), имеем

7) Наконец, подставляя (2,5) из (6) в (1), получаем

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

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

В теории общерекурсивных функций проблема выводимости занимает центральное место. Поэтому нам сейчас необходимо более детально рассмотреть эту проблему.

Прежде всего дадим более широкое и точное определение понятия «выводимость». Для этого сперва определим понятие «терм», а затем понятия «равенство» и «вывод».

Назовем буквы, которые мы раньше обычно применяли для обозначений функций

функциональными буквами. Список функциональных букв неограничен.

Переменные, как и раньше, будем обозначать буквами

Понятие «терм» определим индуктивно:

1) 0 есть терм.

2) Каждая переменная есть терм.

3) R есть терм, если R — терм.

есть терм, если — функциональная буква, — термы.

5) Иных термов нет.

Приведем примеры выражений, которые являются термами:

1. Цифра 3 есть терм, так как 0 есть терм, — терм, есть терм и тоже терм.

2. Любая постоянная есть терм. Постоянные в дальнейшем будем обозначать теми же буквами, которые приняты для обозначения переменных, но со звездочками:

3. есть терм. Термами являются также

4. .

5. .

6. .

7. .

Примеры выражений, которые не являются термами: .

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

Выражение , где R и S — термы, назовем равенством.

Осталось точно определить правила вывода новых равенств из заданной системы равенств Е. Будем считать, что разрешается:

Операция 1. Подставлять числа на место переменных.

Операция 2. Переходить от выражений вида , не содержащих переменных ( — термы), к выражению, получающемуся из путем замены в одном или нескольких местах одновременно вхождений Н на .

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

Обратим внимание на то, что схема определения примитивно-рекурсивных функций наделена следующими двумя свойствами:

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

б) Схема является определением с помощью математической индукции.

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

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

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

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

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

Однозначность здесь означает, что нельзя одновременно вывести из системы Е два противоречивых равенства.

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

Но как организовать этот вывод? Как найти это число Можно, конечно, попробовать выводить из Е все возможные равенства до тех пор, пока не встретится равенство, интересующее нас. Однако при таком подходе нет никакой гарантии, что этот процесс не продлится неопределенно долго. Ведь даже в конечном лабиринте, если неразумно организован поиск, можно как угодно долго ходить по коридорам и площадкам и все-таки не найти нужной площадки (в связи с тем, что конечный лабиринт может содержать коридоры, замкнутые в цикл).

Процессу перебора можно придать определенную регулярность так, чтобы этот процесс годился и для вывода равенства в конечное, но не ограниченное заранее число шагов.

Мы не будем приводить здесь описания этого процесса. Оказывается, что путем гёделизации процесс перебора всех выводов сводится к применению оператора наименьшего числа.

Введение в рассмотрение этого оператора приводит к иному способу определения класса рекурсивных функций.