11.8. Оценки скорости роста. Функция Аккермана

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

Теорема 81. Существует всюду определённая вычисли­мая функция двух аргументов, универсальная для класса всех примитивно рекурсивных функций одного аргумен­та.

Очевидно, что если U — такая функция, то функ­ция d, для которой d{n) = U(п, п) + 1, будет всюду опре­делённой, вычислимой и будет отличаться от любой при­митивно рекурсивной функции (от п-ой — в точке п).

<] Всякая примитивно рекурсивная функция получа­ется из базисных с помощью некоторой последовательно­сти операций подстановки и рекурсии. Ясно, что такую последовательность можно описать словом в конечном алфавите — так сказать, программой (в которой после­довательно определяются различные примитивно рекур­сивные функции и для каждой написано, из каких других она получается и с помощью каких операций). Из всех программ отберём программы для одноместных функ­ций (разумеется, в качестве промежуточных функций можно использовать функции с любым числом аргумен­тов). Множество таких программ разрешимо, их можно пронумеровать вычислимым образом. Функция (п, х) н->-

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

Однако интересно указать и более конкретную причи­ну, мешающую некоторым вычислимым функциям быть примитивно рекурсивными. Вот одна из возможностей: примитивно рекурсивные функции не могут быстро ра­сти. Эта идея восходит к Аккерману, который построил функцию, растущую быстрее всех примитивно реку рейв-ных — функцию Аккермана. Сейчас мы изложим эту кон­струкцию (хотя детали построения будут иными).

Определим последовательность функций «о, а\,... от одного аргумента. (Все эти функции будут всюду опре­делёнными.) Положим «о(ж) = х + 1. Определяя а,-, мы будем использовать такое обозначение: /М(х) означа­ет /(/(... f(x) ...)), где функция / использована п раз. Так вот,

а,-(ж) = а;-_1 '(х)

(почему удобно применять функцию а,-_1 ровно ж+ 2 ра­за, мы увидим чуть позже).

Очевидные свойства (формально их можно доказать по индукции):

• а;(ж) > х при всех г и ж;

• а,-(ж) возрастает с возрастанием х;

• а,-(ж) возрастает с возрастанием г (для каждого фиксированного х);

• а;(ж) ^ а,-_1(а,-_1(ж)).

Теперь можно оценить скорость роста любой прими­тивно рекурсивной функции.

Теорема 82. Пусть / — примитивно рекурсивная функция п аргументов. Тогда найдётся такое к, что

f(xlхп) ^ аА(тах(ш1,..., хп))

при всех Х\ ,..., хп.

<] Идея проста — можно оценить скорость роста ком­позиции функций, зная оценки для каждой из них; анало­гично для рекурсии. Формально говоря, доказательство использует «индукцию по построению» примитивно ре­курсивных функций.

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

f(x) = д(к1(х)./..../кк(х))

(для краткости мы пишем одну букву х, имея в виду вектор переменных). Пусть еедг оценивает все функ­ции h\,...,hk и функцию д сверху, то есть /г,-(х) <С <С адг(тах(ш)) при всех г и ж, а также д(у) <С адг(тах(г/)) (здесь тах(и) означает максимальный элемент в набо­ре и). Тогда f(x) не превосходит

aN(max(hi(x),..., hk(x))) ^ oK(ew(s:)) ^ aN+i(x)

(мы пользуемся указанными выше свойствами функ­ций а,-).

Похоже (но немного сложнее) дело обстоит с рекурси­ей. Пусть функция / определяется рекурсивно:

f(x,0)=g(x); f{x, п + 1) = h{x, п, f{x, п)).

(Здесь х также обозначает набор нескольких перемен­ных.) Пусть функции д и h оцениваются сверху функци­ей Off - Тогда

f(x, 1) = h(x, О, f(x, 0)) ^ aAr(max(ai, 0, f(x, 0))) ^

<С адг(тах(ш, 0, адг(тах(ш)))) <С адг(адг(тах(ш)))

(в последнем переходе мы пользуемся тем, что адг(2) > i). Аналогично f{x, 2) <С адг(адг(адг (тах(ш)))) и вообще

f(x,i) <С o|.+1'(max(i:)) <С адг+i (тах(г, тах(ш))),

что и требовалось доказать. >

Заметим, что каждый оператор подстановки или ре­курсии увеличивает номер верхней оценки на 1, так что функция, в определении которой не более 100 операторов, растёт не быстрее ащ.

Очевидным следствием полученной оценки является такое утверждение:

Теорема 83. Функция А{п) = ап{п) растёт быстрее любой примитивно рекурсивной функции.

Отметим, что определение функции Аккермана (точ­нее, функции (п,х) и-)- ап{х)) вполне можно назвать ре­курсивным — одно значение этой функции определяетсячерез другие, с меньшим первым аргументом. Оно явля­ется примером рекурсивного определения, не сводящего­ся к примитивной рекурсии.

88. Покажите, что прямой пересчёт (в возрастающем по­рядке) бесконечного примитивно рекурсивного множества может не быть примитивно рекурсивным.

89. Покажите, что функция, обратная к примитивно ре­курсивной биекции г: N —> М, может не быть примитивно ре­курсивной.