Рекурсивные функции

h(x1,...,xk,0)=f(x1,...,xk);
h(x1,...,xk,y+1)=g(x1,...,xk,y,h(x1,...,xk,y)).

sum(x,0)=x;
     sum(x,y+1)=sum(x,y)+1.

prod(x,0)=0;
     prod(x,y+1)=prod(x,y)+x.

Примитивно рекурсивные множества

Будем называть множество примитивно рекурсивным, если его характеристическая функция примитивно рекурсивна. (Вариант: если оно является множеством нулей примитивно рекурсивной функции; это то же самое, так как можно сделать подстановку в функцию $$x \mapsto 1\subtr x$$.)

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

Свойства x=y и $$x \ne y$$ примитивно рекурсивны ( x=y тогда и только тогда, когда $$(x\subtr y) + (y\subtr x)=0$$ ).

Функция f(x), заданная соотношением

f(x) = [ if  R(x) then g(x) else h(x) fi ],

будет примитивно рекурсивной, если таковы функции g и h и свойство R. В самом деле, f(x) можно записать как $$r(x)g(x)\hm+(1\subtr r(x))h(x)$$, где r характеристическая функция свойства R.

Теперь можно записать формулу для прибавления единицы по модулю n (для чисел, меньших n ):

x+1 mod n = [ if x+1 = n then 0 else x+1 fi ]

После этого функцию x mod n (остаток от деления на n ) можно определить рекурсивно:

0 mod n = 0;
(x+1) mod n = (x mod n) + 1 mod n.

Покажем, что ограниченные кванторы, примененные к примитивно рекурсивным свойствам (множествам), дают снова примитивно рекурсивные свойства. Это означает, например, что если свойство R(x,y) примитивно рекурсивно, то свойства

$$S(x,z)=(\exists\ y\ \le z) R(x,y)$$

и

$$T(y,z)=(\forall\ y \le z) R(x,y)$$

также примитивно рекурсивны. Чтобы убедиться в этом, заметим, что для функций ограниченный квантор соответствует перемножению или суммированию: если свойство R(x,y) равносильно r(x,y)=0, то

$$S(x,z)\Leftrightarrow\left[\prod\limits_{y=0}^{z} r(x,y) = 0\right].$$

А произведение легко определить рекурсивно:

$$\begin{align*} % \prod\limits_{y=0}^{0} r(x,y)= r(x,0);\\ \prod\limits_{y=0}^{t+1} r(x,y)= \left[\prod\limits_{y=0}^{t}r(x,y)\right]\cdot r(x,t+1); % \end{align*}$$

с суммированием можно поступить аналогичным образом.

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

Покажем теперь, что если график некоторой функции f примитивно рекурсивен и ее значения ограничены сверху некоторой примитивно рекурсивной функцией g, то сама функция f примитивно рекурсивна. В самом деле, если r характеристическая функция графика, то есть r(x,y)=1 при y=f(x) и r(x,y)=0 при $$y \ne f(x)$$ (для простоты мы рассматриваем случай функций одного аргумента), то

$$f(x) = \sum\limits_{y=0}^{\infty} y\cdot r(x,y),$$

а суммирование можно ограничить сверху выражением g(x) и воспользоваться примитивной рекурсивностью ограниченной суммы.

Отсюда легко вывести следующее утверждение: если функция g и свойство R(x,y) примитивно рекурсивны, то функция x $$\mapsto$$ f(x) = наименьшее y <= g(x), для которого R(x,y) (если для некоторого x такого y нет, то полагаем значение функции равным, скажем, g(x)+1 ) будет примитивно рекурсивной. В самом деле, график функции f легко описать с помощью ограниченных кванторов.

Такой способ определения функции называют ограниченным оператором минимизации в отличие от неограниченного, где нет заранее известной границы g(x). Как мы увидим, в неограниченном случае получающаяся функция не обязана быть примитивно рекурсивной.

Ограниченный оператор минимизации можно использовать, чтобы убедиться, что функция x $$\mapsto$$ (минимальное простое число, большее x ) примитивно рекурсивна (рассуждение Евклида о бесконечности множества простых чисел устанавливает, что это число не превосходит x!+1, а факториал примитивно рекурсивен). После этого функция n $$\mapsto$$ ( n -е простое число) легко определяется с помощью рекурсии.

Другие виды рекурсии

Слова " рекурсивное определение функции" можно понимать и в более широком смысле, нежели мы это делали (см. выше определение рекурсии, или примитивной рекурсии) как любой способ задания функции, который связывает значение функции в данной точке с другими ее значениями. Как мы увидим ниже при обсуждении функции Аккермана, есть такие схемы рекурсивных определений, которые выводят из класса примитивно рекурсивных функций. Но есть и такие, которые можно свести к рассмотренной нами схеме.

Мы приведем два примера последнего типа: совместное определение нескольких функций и использование произвольных меньших значений аргумента.

Совместная рекурсия. Пусть две одноместные функции f и g заданы соотношениями:

f(0) = a,
g(0) = b,
f(n+1) = F(n,f(n),g(n)),
g(n+1) = G(n,f(n),g(n)),

где a и b некоторые числа, а функции F и G примитивно рекурсивные функции трех аргументов. Покажем, что тогда функции f и g примитивно рекурсивны.

Чтобы доказать это, нам потребуется примитивно рекурсивная нумерация пар такая функция $$\langle x,y \rangle \hm\to [x,y]$$ (номер пары мы обозначаем квадратными скобками), которая была бы примитивно рекурсивна вместе с двумя обратными функциями (дающими по номеру пары ее первый и второй члены). Тогда мы сможем написать рекурсивное определение для функции h(n)=[f(n),g(n)]:

h(0) = [a,b],
h(n+1) = [F(n,p1(h(n)),p2(h(n))),G(n,p1(h(n)),p2(h(n)))],

где функции p1 и p2 дают по номеру пары первый и второй ее члены. Если функция h примитивно рекурсивна, то и функции f и g (композиции h с функциями p1 и p2 ) также примитивно рекурсивны.

Осталось объяснить, как найти примитивно рекурсивную нумерацию пар. Можно заметить, что есть многочлен второго порядка с двумя переменными, задающий взаимно однозначное соответствие N x N -> N. Это соответствие видно из таблицы:

6
 3  7 
 1  4  8 
 0  2  5  9

Примитивную рекурсивность обратных отображений p1 и p2 можно установить, воспользовавшись ограниченной минимизацией, так как p1(n) есть минимальное x <= n, для которого найдется y <= n, при котором [x,y]=n.

Менее симметричная нумерация пар может быть задана формулой [a,b]=(2a+1)2b-1. Можно также заметить, что нам не нужно, чтобы все числа были номерами каких-то пар, и воспользоваться нумерацией [a,b]=2a3b.

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

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

Теорема 74. Пусть функция g одного аргумента примитивно рекурсивна, причем g(x)<x при x>0 ; пусть F примитивно рекурсивная функция двух аргументов; пусть c произвольная константа. Тогда функция h, определенная соотношениями

h(0) = c,
h(x) = F(x,h(g(x))) при x>0

примитивно рекурсивна.

Чтобы доказать эту теорему, используем следующую нумерацию конечных последовательностей натуральных чисел: номером пустой последовательности считаем число 1, номером одноэлементной последовательности $$\langle a\rangle$$ считаем число 2a+1, последовательность $$\langle a,b\rangle$$ имеет номер 2a+13b+1, последовательность $$\langle a,b,c\rangle$$ имеет номер 2a+13b+15c+1 и так далее (основания степеней простые числа). Будем обозначать номер последовательности $$\langle a,b,...,z\rangle$$ через [a,b,...,z]. Эта нумерация в некотором смысле примитивно рекурсивна. Конечно, буквально это понимать нельзя, так как нумерация представляет собой " функцию с переменным числом аргументов". Но разные связанные с ней функции примитивно рекурсивны. В частности, таковы функции

Length(x) = длина последовательности с номером x ;

Select(i,x)=i -ый член последовательности с номером x ;

Append(x,y)= номер последовательности, которая получается приписыванием числа y к последовательности с номером x.

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

Теперь мы докажем, что функция

$$x \mapsto H(x)=[h(0),h(1),...,h(x)]$$

примитивно рекурсивна. В самом деле, H(0)=[c], а

H(k+1)= Append(H(k),F(k+1,Select(g(k+1),H(k)))).

Машины Тьюринга и рекурсивные функции

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

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

Напомним, что мы считаем входом и выходом машины Тьюринга слова из нулей и единиц. Поскольку аргументами и значениями примитивно рекурсивных функций являются числа, теорема будет иметь смысл, только если мы договоримся отождествлять числа и слова. Как уже говорилось, мы отождествляем число n со словом, которое получается после удаления старшего бита 1 в двоичном разложении числа n+1.

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

Теперь рассмотрим итерированную функцию перехода, которая говорит, каково будет состояние машины Тьюринга после t шагов. Точнее, тут имеются четыре функции от пяти аргументов (первые четыре аргумента кодируют состояние, пятый представляет собой число шагов). Их определение имеет вид совместной рекурсии, которую мы только что разобрали. Поэтому эти функции примитивно рекурсивны. Будем считать, что после появления заключительного состоянии конфигурация машины не меняется. Если мы знаем, что число шагов работы ограничено примитивно рекурсивной функцией, то достаточно подставить ее на место пятого аргумента (числа шагов), чтобы убедиться, что заключительная конфигурация машины является примитивно рекурсивной функцией от ее начальной конфигурации. Следовательно, результат работы является примитивно рекурсивной функций начального данного.

Это рассуждение неявно использует примитивную рекурсивность различных функций, связанных с переходом от одного представления данных к другому. Например, вход машины Тьюринга является двоичным словом, которое мы договорились отождествлять с некоторым числом x. Этому входу соответствует начальная конфигурация машины Тьюринга, которую мы кодируем четверкой чисел. Нам важно, что эта четверка примитивно рекурсивно зависит от x. Это легко понять, так как преобразование связано с переходом от одной системы счисления к другой (одно и то же слово кодирует разные числа в разных системах счисления); примитивную рекурсивность таких функций легко установить с помощью описанных выше методов. Кроме того, нам надо из выходной конфигурации примитивно рекурсивно извлечь результат и также перекодировать его, а также по входу получить его длину (чтобы подставить в примитивно рекурсивную функцию, ограничивающую число шагов). Но все это также не выходит из круга разобранных выше приемов, и подробно останавливаться на этом мы не будем.

Эта теорема убеждает нас в примитивной рекурсивности многих довольно сложно определяемых функций. Например, рассмотрим функцию n $$\mapsto$$ ( n -ый десятичный знак числа $$\pi$$ ). Известно, что вычислены миллионы таких знаков, поэтому есть все основания полагать, что известные алгоритмы работают не слишком долго было бы очень странно, если бы время их работы (даже учитывая неудобство машины Тьюринга для программирования) не оценивалось бы, скажем, функцией cx 2n при достаточно большом c. А такая оценка примитивно рекурсивна, что позволяет сослаться на только что доказанную теорему. (На самом деле тут большой запас существуют примитивно рекурсивные функции, которые растут гораздо быстрее 2n.)

Другое описание класса примитивно рекурсивных функций, более понятное программистам: это функции, которые можно вычислять программой, содержащей if-then-else -ветвления и for -циклы, но не содержащие while -циклов (и тем более go to и разных других пакостей типа изменения параметра for-цикла внутри цикла).

  87. Сформулируйте и докажите соответствующее утверждение.

Частично рекурсивные функции

Операторы примитивной рекурсии и подстановки не выводят нас из класса всюду определенных функций. Не так обстоит дело с оператором минимизации, о котором мы уже упоминали. Он применяется к (k+1) -местной функции f и дает k -местную функцию g, определяемую так: g(x1,...,xk) есть наименьшее y, для которого f(x1,...,xk,y)=0.

Смысл выделенных слов ясен, если функция f всюду определена. Если нет, то понимать их надо так: значение g(x1,...,xk) равно y, если f(x1,...,xk,y) определено и равно нулю, а все значения f(x1,...,yk,y') при y'<y определены и не равны нулю.

Часто используется обозначение

$$g(x_{1},\dots ,x_{k})=\mu y(f(x_{1},\dots ,x_{k},y)=0),$$

и потому оператор минимизации также называют $$\mu$$ -оператором.

Ясно, что такое определение обеспечивает вычислимость g, если вычислима f (мы перебираем в порядке возрастания все y, ожидая появления нулевого значения).

  88. Покажите, что если изменить определение и разрешить f(x1,...,xk,y') быть не определенным при y'<y, то функция g может быть невычислимой при вычислимой f.

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

Такая странная терминология, видимо, сложилась в результате переводов с английского. По-английски были "primitive recursive functions" (примитивно рекурсивные функции). Затем было дано более общее (general) понятие вычислимой всюду определенной функции, и такие функции были названы "general recursive functions". Затем стали рассматривать и частичные (partial) вычислимые функции, называя их "partial recursive functions". В русском же языке слово "partial" попало не туда, и вместо частичных рекурсивных функций стали говорить о частично рекурсивных функциях. Та же участь постигла и слово "general", которое странным образом вошло в прилагательное " общерекурсивная" и означает, что функция всюду определена.

Теорема 76. Всякая функция, вычислимая с помощью машины Тьюринга, является частично рекурсивной.

Пусть f вычислимая с помощью машины Тьюринга (обозначим эту машину через M ) функция одного аргумента. Рассмотрим свойство T(x,y,t), состоящее в том, что машина M на входе x дает ответ y за время не более чем t. Как мы видели выше, по входу машины Тьюринга и по времени t можно примитивно рекурсивно вычислить ее состояние в момент t ; ясно, что можно также узнать, закончила ли она работу, и если да, то был ли ответ равен y. Итак, свойство T примитивно рекурсивно.

Теперь объединим аргументы y и t в пару с помощью примитивно рекурсивной нумерации; получится примитивно рекурсивная функция T', для которой T'(x,[y,t])=T(x,y,t) ; теперь можно написать $$f(x)=p_{1} (\mu\ z\ T'(x,z))$$, где p1 дает по номеру пары ее первый член, а $$\mu z$$ означает " наименьшее z, для которого, ...". Таким образом, функция f является частично рекурсивной.

Верно и обратное: Теорема 77. Всякая частично рекурсивная функция вычислима на машине Тьюринга.

Легко написать программу с конечным числом переменных, вычисляющую любую частично рекурсивную функцию (подстановка сводится к последовательному выполнению программ, рекурсия к циклу типа for, минимизация к циклу типа while ; оба вида циклов легко реализуются с помощью операторов перехода).

После этого остается только сослаться на то, что всякая функция, вычисляемая программой с конечным числом регистров, вычислима на машине Тьюринга (как мы видели в разделе 10.2, теорема 66).

Поэтому если мы верим в " тезис Тьюринга", гласящий, что всякая вычислимая функция вычислима на машине Тьюринга, то должны верить и в " тезис Черча" (всякая вычислимая функция частично рекурсивна), так что эти тезисы равносильны.

На самом деле история здесь сложнее и примерно может быть описана так. Определение примитивно рекурсивной функции было дано великим логиком Куртом Геделем и использовано как техническое средство при доказательстве теоремы Геделя о неполноте, в начале 1930-х годов. Он же дал определение общерекурсивной функции (не совпадающее с приведенным нами, но эквивалентное ему). Американский логик Алонзо Черч сформулировал свой тезис для всюду определенных функций, предположив, что всякая вычислимая всюду определенная функция является общерекурсивной. Затем американский математик Клини предложил распространить этот тезис на функции, не являющиеся всюду определенными.

Параллельно английский математик Тьюринг и американский математик Пост предложили свои модели абстрактных вычислительных машин (машины Тьюринга и Поста), отличающиеся лишь некоторыми деталями, и высказали предположение о том, что такие машины покрывают весь класс алгоритмических процессов. Вскоре стало ясно, что вычислимость функции на таких машинах равносильна частичной рекурсивности. (Исторические подробности можно узнать из книги Клини [4].)

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

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

Наше доказательство теорем 76 и 77 позволяет также получить такое следствие, называемое иногда теоремой Клини о нормальной форме:

Теорема 78. Всякая частично рекурсивная функция f представима в виде

$$f(x)=a(\mu z (b(x,z)=0)),$$

где a и b некоторые примитивно рекурсивные функции.

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

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

  89. Покажите, что одним $$\mu$$ -оператором, применяя его последним, не обойтись: не всякая частично рекурсивная функция представима в виде

$$f(x)=\mu z (b(x,z)=0)$$

где b некоторая примитивно рекурсивная функция.

Из теоремы Клини о нормальной форме вытекает такое утверждение:

Теорема 79. Всякое перечислимое множество есть проекция примитивно рекурсивного множества.

Перечислимое множество есть область определения рекурсивной функции; представив ее в нормальной форме, видим, что область определения есть проекция множества $$\{\langle x,z\rangle \mid b(x,z)\hm=0\}$$.

Вычислимость с оракулом

Определение класса частично рекурсивных функций легко модифицировать для случая вычислимости с оракулом. Пусть имеется некоторая всюду определенная функция $$\alpha.$$ Рассмотрим класс $$F[\alpha ]$$, который состоит из базисных функций, функции $$\alpha$$ и всех других функций, которые могут быть из них получены с помощью подстановки, примитивной рекурсии и минимизации.

(Формально можно сказать так: $$F[\alpha ]$$ есть минимальный класс, который содержит базисные функции, функцию $$\alpha$$ и замкнут относительно подстановки, примитивной рекурсии и минимизации. Такой минимальный класс существует достаточно взять пересечение всех классов с этими свойствами.)

Теорема 80. Класс $$F[\alpha ]$$ состоит из всех функций, вычислимых с оракулом $$\alpha$$ (то есть с помощью программ, вызывающих $$\alpha$$ как внешнюю процедуру).

Прежде всего заметим, что все функции из класса $$F[\alpha ]$$ вычислимы с помощью таких программ. Это можно объяснить, например, так. Программы с конечным числом переменных вычисляли все частично-рекурсивные функции. Если добавить к ним примитивную операцию вычисления значения функции $$\alpha$$ в заданной точке, то они точно так же будут вычислять все функции из класса $$F[\alpha ]$$.

Более содержательно обратное утверждение: мы хотим доказать, что если некоторая (частичная, вообще говоря) функция вычислима относительно $$\alpha,$$ то она может быть получена из базисных функций и из $$\alpha$$ с помощью подстановки, рекурсии и минимизации.

Для этого вспомним критерий относительной вычислимости (теорема 45). Пусть функция f вычислима относительно всюду определенной функции $$\alpha.$$ Тогда, как мы знаем, существует перечислимое множество W троек вида $$\langle x,y,t\rangle$$, где x и y натуральные числа, а t образцы (функции с конечной областью определения), которое является корректным (тройки с одинаковым x, но разными y содержат несовместные образцы) и для которого

$$f(x)=y \Leftrightarrow \exists t\; (\langle x,y,t\rangle \in W \text{ и $t$~есть часть функции~$\alpha$}).$$

Мы сейчас покажем, что свойство " t есть часть функции $$\alpha$$ " является примитивно рекурсивным относительно $$\alpha:$$ его характеристическая функция получается из базисных функций и из $$\alpha$$ с помощью операций подстановки и рекурсии. (Напомним, что мы отождествляем образцы с их номерами в какой-то нумерации; о ее выборе см. ниже.)

После этого останется записать W как проекцию примитивно рекурсивного множества ( $$\langle x,y,t\rangle \hm\in W \hm\Leftrightarrow {\exists u\: (v(x,y,t,u)=0)}$$, где v примитивно рекурсивна), и заметить, что

$$f(x)=p_{1}(\mu z v'(x,z)=0).$$

Здесь v' примитивно рекурсивная относительно $$\alpha$$ функция, для которой v'(x,[y,t,u])=0 тогда и только тогда, когда v(x,y,t,u)=0 и t есть часть функции $$\alpha,$$ а функция p1 выделяет из номера тройки [y,t,u] ее первый член y.

Осталось показать, что множество $$\{ t | образец\ с \номером\ t\ есть\ часть\ функции\ \alpha \}$$ является примитивно рекурсивным относительно $$\alpha.$$ При доказательстве мы будем предполагать, что нумерация образцов такова, что следующие функции примитивно рекурсивны (они определены для образцов с непустой областью определения; для пустого образца доопределим их как угодно):

last-x(t) наибольшее из чисел, на котором определен образец с номером t ;

last-y(t) значение функции-образца с номером t в максимальной точке своей области определения;

all-but-last(t) номер образца, который получится из образца с номером t, если удалить максимальную точку области определения.

Тогда можно записать такое рекурсивное определение: образец с номером t есть часть функции $$\alpha,$$ если либо этот образец пуст, либо $$\alpha (last-x(t))= last-y(t)$$ и образец с номером all-but-last(t) есть часть функции $$\alpha.$$

Это определение использует " возвратную рекурсию", которая разобрана в теореме 74; значение функции определяется рекурсивно через ее значения в меньших точках. Надо только выбрать нумерацию образцов так, чтобы all-but-last(t) было меньше t для всех t. Этого несложно добиться: например, можно нумеровать образцы с помощью простых чисел, считая, что образец $$\{\langle a,b \rangle,\dots,\langle e,f\rangle\}$$ имеет номер pa(b+1)... pe(f+1), где pi простое число с номером i (так что p0=2, p1=3, p2=5, ...).

Заметим, что доказательство стало бы немного проще, если использовать только " сплошные образцы" (областью определения которых является некоторый начальный отрезок натурального ряда) тогда можно начать с того, что установить примитивную рекурсивность (относительно $$\alpha$$ ) функции n $$\mapsto$$ $$[\alpha (0),\alpha (1),\dots ,\alpha (n)]$$. Легко понять также, что в определении относительной вычислимости можно ограничиться только сплошными образцами.

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

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

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

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

Всякая примитивно рекурсивная функция получается из базисных с помощью некоторой последовательности операций подстановки и рекурсии. Ясно, что такую последовательность можно описать словом в конечном алфавите так сказать, программой (в которой последовательно определяются различные примитивно рекурсивные функции и для каждой написано, из каких других она получается и с помощью каких операций). Из всех программ отберем программы для одноместных функций (разумеется, в качестве промежуточных функций можно использовать функции с любым числом аргументов). Множество таких программ разрешимо, их можно пронумеровать вычислимым образом. Функция $$\langle n,x\rangle \hm\mapsto$$ (результат применения функции, заданной программой номер n, к числу x ) будет вычислима и по построению будет универсальной для класса примитивно рекурсивных функций.

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

Определим последовательность функций $$\alpha _{0},\alpha _{1},..$$. от одного аргумента. (Все эти функции будут всюду определенными.) Положим $$\alpha _{0}(x)=x+1$$. Определяя $$\alpha _{i}$$, мы будем использовать такое обозначение: f[n](x) означает f(f(...f(x)...)), где функция f использована n раз. Так вот,

$$\alpha_{i} (x) = \alpha_{i-1}^{[x+2]}(x)$$

(почему удобно применять функцию $$\alpha _{i-1}$$ ровно x+2 раза, мы увидим чуть позже).

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

$$\alpha _{i} (x)>x$$ при всех i и x ;

$$\alpha _{i} (x)$$ возрастает с возрастанием x ;

$$\alpha _{i} (x)$$ возрастает с возрастанием i (для каждого фиксированного x );

$$\alpha _{i} (x) \ge \alpha _{i-1}(\alpha _{i-1}(x))$$.

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

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

$$f(x_{1},\dots ,x_{n}) \le \alpha _{k} (max(x_{1},\dots ,x_{n}))$$

при всех x1,...,xn.

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

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

f(x)=g(h1(x),...,hk(x))

(для краткости мы пишем одну букву x, имея в виду вектор переменных). Пусть $$\alpha _{N}$$ оценивает все функции h1,...,hk и функцию g сверху, то есть $$h_{i}(x)\le \alpha _{N}(max(x))$$ при всех i и x, а также $$g(y) \le \alpha _{N}(max(y))$$ (здесь max(u) означает максимальный элемент в наборе u ). Тогда f(x) не превосходит

$$\alpha _{N}(max(h_{1}(x),\dots ,h_{k}(x))) \le \alpha _{N}(\alpha _{N}(x)) \le \alpha _{N+1}(x)$$

(мы пользуемся указанными выше свойствами функций $$\alpha _{i}$$ ).

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

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

(Здесь x также обозначает набор нескольких переменных.) Пусть функции g и h оцениваются сверху функцией $$\alpha _{N}$$. Тогда

$$f(x,1)=h(x,0,f(x,0)) \le \alpha _{N} (max(x,0,f(x,0))) \le \alpha _{N}(max(x,0,\alpha _{N}(max(x)))) \le \alpha _{N}(\alpha _{N}(max(x)))$$

(в последнем переходе мы пользуемся тем, что $$\alpha _{N}(t)>t$$ ). Аналогично $$f(x,2) \le \alpha _{N}(\alpha _{N}(\alpha _{N}(max(x))))$$ и вообще

$$f(x,i)\le \alpha_N^{[i+1]}(\max(x))\le \alpha_{N+1}(\max(i,\max(x))),$$

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

Заметим, что каждый оператор подстановки или рекурсии увеличивает номер верхней оценки на 1, так что функция, в определении которой не более 100 операторов, растет не быстрее $$\alpha _{101}$$.

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

Теорема 83. Функция $$A(n)=\alpha _{n}(n)$$ растет быстрее любой примитивно рекурсивной функции.

Отметим, что определение функции Аккермана (точнее, функции $$\langle n,x\square$$ $$\mapsto$$ $$\alpha _{n}(x)$$ ) вполне можно назвать рекурсивным одно значение этой функции определяется через другие, с меньшим первым аргументом. Оно является примером рекурсивного определения, не сводящегося к примитивной рекурсии.

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

  91. Покажите, что функция, обратная к примитивно рекурсивной биекции i : N -> N, может не быть примитивно рекурсивной.

  92. Покажите, что для любой одноместной примитивно рекурсивной функции h и для любой трехместной примитивно рекурсивной функции g рекурсивное определение

f(x,0)= h(x);
f(x,i+1)= g(x,i, f(2x,i))

задает примитивно рекурсивную функцию.