Главная > Разное > Логика, автоматы, алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 12.8. Пример построения вычислимой, но не примитивно-рекурсивной функции

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

Верно ли обратное утверждение? Всякая ли вычислимая функция примитивно-рекурсивна?

Отрицательный ответ на эти вопросы был дан почти одновременно Петер и Аккерманом, которые, идя совершенно различными путями, построили примеры вычислимой, но не примитивно-рекурсивной функции.

Познакомимся с идеей примера Петер.

Р. Петер впервые обратила внимание на то, что множество примитивно-рекурсивных функций является счетным множеством.

Действительно, класс первоначальных функций счетен (так как число различных переменных и констант q счетно). Следовательно, счетен класс примитивно-рекурсивных функций, определенных с помощью одного применения схем IV или V, потому что счетно множество наборов для схемы IV или пар Для схемы V, образованных из элементов счетного класса.

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

Петер удалось все примитивно-рекурсивные функции одной переменной эффективно перенумеровать, т. е. расположить их в последовательность

(12.14)

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

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

Но так как в ряду (12.14) содержатся все примитивно-рекурсивные функции одной переменной, то нашелся бы такой номер , что

для всех . Иначе

Так как это равенство должно выполняться для всех , то, в частности, оно должно выполняться и для . Но тогда

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

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

Расширение класса примитивно-рекурсивных функций было предложено Гёделем в 1934 г. и основано на одной смелой идее Эрбрана.

<< Предыдущий параграф Следующий параграф >>
Оглавление