% исправлены опечатки 20.04.2000
\chapter{Рекурсивные функции}\label{chapt11}
        \index{Функция!рекурсивная}%
        \index{Рекурсивная функция}%

\section{Примитивно рекурсивные функции}\label{chapt11-1}

        \index{Примитивно рекурсивная функция}%
        \index{Функция!примитивно рекурсивная}%
Программы с конечным числом переменных напоминали ассемблер;
рассматриваемые в этом разделе рекурсивные функции скорее
напоминают функциональное программирование, когда одни функции
определяются через другие. Мы будем рассматривать функции с
натуральными аргументами и значениями. Вообще говоря, функции
могут быть не всюду определенными, так что говоря о функции
$n$~аргументов (функции из~$\bbN^n$ в~$\bbN$, $n$\д местной функции),
мы имеем
в виду функцию, определённую на некотором подмножестве~$\bbN^n$
со значениями в~$\bbN$.

Пусть имеется $k$\д местная функция~$f$ и $k$~штук $n$\д местных
функций~$g_1,\dots,g_k$. Тогда из них можно сформировать одну $n$\д местную
функцию
        $$
\langle x_1,\dots,x_n\rangle \mapsto
   f(g_1(x_1,\dots,x_n),\dots,g_k(x_1,\ldots,x_n)).
        $$
Говорят, что определённая таким образом функция
получена из функций~$f$ и~$g_1,\dots,g_k$
        \index{Подстановка}%
с помощью операции \emph{подстановки}.

Другая операция, называемая операцией \emph{рекурсии}, или
        \index{Рекурсия}%
        \index{Рекурсия!примитивная}%
\emph{примитивной рекурсии}, применяется к $k$\д местной
функции~$f$ и $(k\hm+2)$\д местной функции~$g$. Её результатом будет
$(k\hm+1)$\д местная
функция~$h$, определяемая так:
        %
\begin{align*}
        %
h(x_1,\ldots,x_k,0)&=f(x_1,\ldots,x_k);\\
h(x_1,\ldots,x_k,y+1)&=g(x_1,\ldots,x_k,y,h(x_1,\ldots,x_k,y)).
        %
\end{align*}
        %
В последовательности
$h(x_1,\dots,x_n,0),h(x_1,\dots,x_n,1),\dots$ каждое значение
определяется через предыдущее, поэтому если какое\д то из значений
не определено, то не определены и все последующие.

Для единообразия будем считать, что нуль\д местные функции
(функции без аргументов) суть константы; это позволяет
рекурсивно определять функции одной переменной.

\emph{Примитивно рекурсивными} называют функции, которые можно
        \index{Примитивно рекурсивная функция}%
        \index{Функция!примитивно рекурсивная}%
получить с помощью операций подстановки и рекурсии из следующих
        \index{Базисная функция}%
\emph{базисных} функций: константы~$0$, операции прибавления
единицы~$s\colon x\hm\mapsto x\hm+1$ и семейства функций проекции: это
семейство для каждого~$k$
содержит $k$~штук $k$\д местных
функций~$\pi_k^i(x_1,\dots,x_k)\hm=x_i$.

Функции проекции позволяют выполнять \лк неоднородные\пк\
подстановки: скажем, можно получить функцию~$\langle x,y\rangle\hm\mapsto
f(g(x),h(y,x,y),x)$ из функций~$f$ и~$h$, комбинируя их с
функциями проекции: сначала получаем функцию~$\langle x,y\rangle
\hm\mapsto g(x)$ (подстановка~$\pi_2^1$ в~$g$), затем~$\langle
x,y\rangle \hm\mapsto h(y,x,y)$ (подстановка
$\pi_2^2,\pi_2^1,\pi_2^2$ в~$h$), затем полученные две функции
вместе с функцией~$\pi_2^1$ подставляем в~$f$.

Подставляя константу~$0$ в функцию прибавления единицы, получаем
константу (функцию нуля аргументов)~$1$. Затем можно получить
константы~$2$,~$3$~\итд

\section[Примеры примитивно рекурсивных функций]
        {Примеры примитивно рекурсивных\\функций}\label{chapt11-2}

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

\textsf{Сложение}. Функция $\langle x,y\rangle \mapsto
        \index{Сложение, рекурсивное определение}%
\opsum(x,y)\hm= x\hm+y$ получается с помощью рекурсии:
        %
\begin{align*}
     \opsum(x,0)&=x;\\
     \opsum(x,y+1)&=\opsum(x,y)+1.
\end{align*}
        %
Надо, конечно, представить правую часть второго равенства как
результат подстановки. Формально говоря, $h(x,y,z)$~в определении
рекурсии надо положить равным~$s(z)$, где $s$\т функция
прибавления единицы.

\textsf{Умножение}. Функция $\langle x,y\rangle \mapsto
        \index{Умножение, рекурсивное определение}%
\opprod(x,y)\hm= xy$ получается с помощью рекурсии
(с использованием сложения):
        %
\begin{align*}
     \opprod(x,0)&=0;\\
     \opprod(x,y+1)&=\opprod(x,y)+x.
\end{align*}

Аналогичным образом можно перейти от умножения к
возведению в степень.

\textsf{Усечённое вычитание}. Мы говорим об \лк усечённом
        \index{Вычитание усечённое, рекурсивное определение}%
вычитании\пк~$x\subtr y\hm= x\hm-y$ при~$x\hm\ge y$ и~$x\subtr y\hm= 0$
при~$x\hm<y$, поскольку мы имеем дело только с натуральными (целыми
неотрицательными) числами. Одноместная функция усечённого вычитания
единицы определяется рекурсивно:
        %
\begin{align*}
     0\subtr 1&=0;\\
     (y+1)\subtr 1&=y.
\end{align*}
        %
(Рекурсия здесь формальна, так как предыдущее значение не
используется.) После этого усечённое вычитание для произвольных
аргументов можно определить так:
        %
\begin{align*}
     x\subtr 0&=x;\\
     x\subtr (y+1)&=(x\subtr y)\subtr 1.
\end{align*}

\section{Примитивно рекурсивные множества}\label{chapt11-3}

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

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

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

Функция~$f(x)$, заданная соотношением
        $$
f(x) = [\textbf{ if } R(x) \textbf{ then }
             g(x) \textbf{ else } h(x)\textbf{ fi }],
        $$
будет примитивно рекурсивной, если таковы функции~$g$ и~$h$ и
свойство~$R$. В самом деле, $f(x)$~можно записать как
$r(x)g(x)\hm+(1\subtr r(x))h(x)$, где $r$\т характеристическая
функция свойства~$R$.

Теперь можно записать формулу для прибавления единицы по
модулю~$n$ (для чисел, меньших~$n$):
        $$
 x+1 \bmod n =
     [\textbf{ if } x+1 = n \textbf{ then } 0
                          \textbf{ else } x+1\textbf{ fi }]
        $$
После этого функцию~$x\hm\bmod n$ (остаток от деления на~$n$) можно
определить рекурсивно:
        %
\begin{align*}
        %
 0 \bmod n &= 0;\\
 (x+1) \bmod n &= (x \bmod n) + 1 \bmod n.
        %
\end{align*}

Покажем, что ограниченные кванторы, применённые к примитивно
        \index{Кванторы!ограниченные}%
        \index{Ограниченный квантор}%
рекурсивным свойствам (множествам), дают снова примитивно рекурсивные
свойства. Это означает, например, что если свойство~$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)\hm=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*}
с суммированием можно поступить аналогичным образом.

После этого легко заметить, что свойство \лк быть простым\пк\
        \index{Простое число}%
примитивно рекурсивно (любое меньшее число либо равно нулю, либо
равно~$1$, либо не является делителем).

Покажем теперь, что если график некоторой функции~$f$ примитивно
рекурсивен и её значения ограничены сверху некоторой примитивно
рекурсивной функцией~$g$, то сама функция~$f$ примитивно
рекурсивна. В самом деле, если $r$\т характеристическая
функция графика, то есть~$r(x,y)\hm=1$ при~$y\hm=f(x)$ и~$r(x,y)\hm=0$
при~$y\hm\ne f(x)$ (для простоты мы рассматриваем случай функций
одного аргумента), то
        $$
f(x) = \sum\limits_{i=0}^{\infty} y\cdot r(x,y),
        $$
а суммирование можно ограничить сверху выражением~$g(x)$ и воспользоваться
примитивной рекурсивностью ограниченной суммы.

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

Такой способ определения функции называют \emph{ограниченным
        \index{Оператор минимизации}%
        \index{Ограниченный оператор минимизации}%
        \index{Минимизации оператор}%
оператором минимизации}\т в отличие от неограниченного, где нет
заранее известной границы~$g(x)$. Как мы увидим, в
неограниченном случае получающаяся функция не обязана быть
примитивно рекурсивной.

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

\section{Другие виды рекурсии}\label{chapt11-4}

Слова \лк рекурсивное определение функции\пк\ можно понимать и в
        \index{Рекурсия}%
более широком смысле, нежели мы это делали (см.~выше определение
рекурсии, или примитивной рекурсии)\т как любой способ задания
функции, который связывает значение функции в данной точке с
другими её значениями. Как мы увидим ниже при обсуждении
функции~Аккермана, есть такие схемы рекурсивных определений, которые
        \index{Функция!Аккермана}%
        \glossary{Аккерман@\Аккерман}%
выводят из класса примитивно рекурсивных функций. Но есть и
такие, которые можно свести к рассмотренной нами схеме.

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

\textsf{Совместная рекурсия}. Пусть две одноместные функции~$f$
        \index{Рекурсия!совместная}%
        \index{Совместная рекурсия}%
и~$g$ заданы соотношениями:
        %
\begin{align*}
        %
f(0) & = a,\\
g(0) & = b,\\
f(n+1) &= F(n,f(n),g(n)),\\
g(n+1) &= G(n,f(n),g(n)),
        %
\end{align*}
        %
где $a$ и~$b$\т некоторые числа, а функции~$F$ и~$G$\т примитивно
рекурсивные функции трёх аргументов. Покажем, что тогда функции~$f$
и~$g$ примитивно рекурсивны.

Чтобы доказать это, нам потребуется примитивно рекурсивная
нумерация пар\т такая функция~$\langle x,y \rangle \hm\to [x,y]$
(номер пары мы обозначаем квадратными скобками), которая была бы
примитивно рекурсивна вместе с двумя обратными функциями
(дающими по номеру пары её первый и второй члены).
Тогда мы сможем написать рекурсивное определение для
функции~$h(n)\hm=[f(n),g(n)]$:
        %
\begin{align*}
        %
h(0)   =& [a,b],\\
h(n+1) =& [F(n,p_1(h(n)),p_2(h(n))),\\
        & \qquad  G(n,p_1(h(n)),p_2(h(n)))],
        %
\end{align*}
        %
где функции~$p_1$ и~$p_2$ дают по номеру пары первый и второй её
члены. Если функция~$h$ примитивно рекурсивна, то и функции~$f$
и~$g$ (композиции~$h$ с функциями~$p_1$ и~$p_2$) также примитивно
рекурсивны.

Осталось объяснить, как найти примитивно рекурсивную нумерацию
пар. Можно заметить, что есть многочлен второго порядка с двумя
переменными, задающий взаимно однозначное
соответствие~$\bbN\hm\times\bbN\hm\to \bbN$. Это соответствие
видно из таблицы:
        %
\begin{center}
\begin{tabular}{cccc}
 6 &  &  &   \\
 3 & 7&  &   \\
 1 & 4& 8&   \\
 0 & 2& 5& 9
\end{tabular}
\end{center}
Примитивную рекурсивность обратных отображений~$p_1$ и~$p_2$
можно установить, воспользовавшись ограниченной минимизацией,
так как $p_1(n)$~есть минимальное~$x\hm\le n$, для которого
найдётся~$y\hm\le n$, при котором~$[x,y]\hm=n$.

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

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

\textsf{Возвратная рекурсия}. Следующее
        \index{Возвратная рекурсия}%
        \index{Рекурсия!возвратная}%
утверждение показывает, что при рекурсивном определении можно
использовать не только значение в предыдущей точке, но и любое
предшествующее значение.

\begin{theorem}
        \label{back-recursion}%
Пусть функция~$g$
одного аргумента примитивно рекурсивна, причём~$g(x)\hm<x$
при~$x\hm>0$; пусть $F$\т примитивно рекурсивная функция двух
аргументов; пусть $c$\т произвольная константа. Тогда
функция~$h$, определённая соотношениями
        %
\begin{align*}
        \label{extended-recursion}%
h(0) & = c,\\
h(x) & = F(x,h(g(x))) \text{ при $x>0$}
        %
\end{align*}
        %
примитивно рекурсивна.
        %
\end{theorem}

%\begin{proof}
        %
$\lhd$\
Чтобы доказать эту теорему, используем следующую нумерацию
        \index{Нумерация!конечных последовательностей}%
конечных последовательностей натуральных чисел: номером пустой
последовательности считаем число~$1$, номером одноэлементной
последовательности~$\langle a\rangle$ считаем число~$2^{a+1}$,
последовательность~$\langle a,b\rangle$ имеет
номер~$2^{a+1}3^{b+1}$, последовательность~$\langle a,b,c\rangle$
имеет номер~$2^{a+1}3^{b+1}5^{c+1}$ и так далее (основания
степеней\т простые числа). Будем обозначать номер
последовательности~$\langle a,b,\dots,z\rangle$
через~$[a,b,\dots,z]$. Эта нумерация в некотором смысле примитивно
рекурсивна. Конечно, буквально это понимать нельзя, так как
нумерация представляет собой \лк функцию с переменным числом
аргументов\пк. Но разные связанные с ней функции примитивно
рекурсивны. В частности, таковы функции
        %
\begin{itemize}
        %
\item $\Length(x) = \text{длина}$ последовательности
                с номером~$x$;
        %
\item $\Select(i,x)=
      \text{$i$\д ый}$ член последовательности с номером~$x$;
        %
\item $\Append(x,y)= \text{номер}$ последовательности,
      которая получается приписыванием числа~$y$ к
      последовательности с номером~$x$.
        %
\end{itemize}
        %
Все эти функции (и другие аналогичные) сводятся к различным
операциям с простыми числами и множителями, которые мы в
сущности уже разбирали.

Теперь мы докажем, что функция
        $$
x \mapsto H(x)=[h(0),h(1),\dots,h(x)]
        $$
примитивно рекурсивна. В самом деле,~$H(0)\hm=[c]$, а
        $$
H(k+1)= \Append(H(k), F(k+1,\Select (g(k+1),H(k)))).\ \rhd
        $$
%\end{proof}

\section[Машины~Тьюринга и рекурсивные функции]
        {Машины~Тьюринга и примитивно\\рекурсивные функции}%
        \label{chapt11-5}

        \index{Машина!Тьюринга}%
        \index{Тьюринга машина}%
        \glossary{Тьюринг@\Тьюринг}%
        \index{Примитивно рекурсивная функция}%
        \index{Функция!примитивно рекурсивная}%
Мы рассмотрели несколько различных приёмов построения примитивно
рекурсивных функций. Тем не менее остаётся не вполне ясным,
насколько этот класс широк. Сейчас мы покажем, что он включает в
себя все достаточно быстро вычислимые функции.

\begin{theorem}
        \label{turing-primitive-recursive}%
Любая функция, вычислимая на машине~Тьюринга не более чем за
        \index{Время вычисления}%
примитивно рекурсивное (от длины входа) время, примитивно
рекурсивна.
        %
\end{theorem}

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

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

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

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

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

\section{Частично рекурсивные функции}\label{chapt11-6}
        \index{Частично рекурсивная функция}%
        \index{Функция!частично рекурсивная}%

Операторы примитивной рекурсии и подстановки не выводят нас из
класса всюду определённых функций. Не так обстоит дело с
\emph{оператором минимизации}, о котором мы уже упоминали. Он
        \index{Оператор минимизации}%
        \index{Минимизации оператор}%
применяется к $(k\hm+1)$\д местной функции~$f$ и даёт $k$\д
местную функцию~$g$, определяемую так: $g(x_1,\dots,x_k)$ есть
\textsl{наименьшее~$y$, для которого~$f(x_1,\dots,x_k,y)=0$}.

Смысл выделенных слов ясен, если функция~$f$~всюду определена. Если нет,
то понимать их надо так: значение $g(x_1,\dots,x_k)$ равно~$y$, если
$f(x_1,\dots,x_k,y)$~определено и равно нулю, а все
значения~$f(x_1,\dots,y_k,y')$ при~$y'\hm<y$ определены и не
равны нулю.

Часто используется обозначение
        $$
g(x_1,\dots,x_k)=\mu y\;(f(x_1,\dots,x_k,y)=0),
        $$
и потому оператор минимизации также называют
        \index{$\mu$\д оператор}%
\emph{$\mu$\д оператором}.

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

\begin{problem}
        %
Покажите, что если изменить определение и
разрешить~$f(x_1,\dots,x_k,y')$ быть не определённым при~$y'\hm<y$, то
функция~$g$ может быть невычислимой при вычислимой~$f$.
        %
\end{problem}

Функции, получающиеся из базисных (нуля, проекции и прибавления
единицы) с помощью операторов подстановки, примитивной рекурсии
и минимизации, называются \emph{частично рекурсивными}. Если
        \index{Функция!частично рекурсивная}%
        \index{Частично рекурсивная функция}%
такая функция оказывается всюду определённой, то её называют
        \index{Функция!общерекурсивная}%
        \index{Общерекурсивная функция}%
\emph{общерекурсивной} функцией.

\begin{historyremark}
        %
Такая странная терминология, видимо, сложилась в результате
переводов с английского. По\д английски были ``primitive
recursive functions'' (примитивно рекурсивные функции). Затем
было дано более общее (general) понятие вычислимой всюду
определённой функции, и такие функции были названы ``general
recursive functions''. Затем стали рассматривать и частичные
(partial) вычислимые функции, называя их ``partial recursive
functions''. В русском же языке слово ``partial'' попало не
туда, и вместо частичных рекурсивных функций стали говорить о
частично рекурсивных функциях. Та же участь постигла и слово
``general'', которое странным образом вошло в прилагательное \лк
общерекурсивная\пк\ и означает, что функция всюду определена.
        %
\end{historyremark}

\begin{theorem}
        \label{turing-to-recursive}%
Всякая функция, вычислимая с помощью машины~Тьюринга,
        \index{Функция!вычислимая на машине Тьюринга}%
        \index{Функция!частично рекурсивная}%
        \index{Частично рекурсивная функция}%
        \index{Тьюринга машина}%
        \index{Машина!Тьюринга}%
        \glossary{Тьюринг@\Тьюринг}%
является частично рекурсивной.
        %
\end{theorem}

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

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

Верно и обратное:
\begin{theorem}
        \label{recursive-to-turing}%
Всякая частично рекурсивная функция вычислима на
        \index{Функция!вычислимая на машине Тьюринга}%
        \index{Функция!частично рекурсивная}%
        \index{Частично рекурсивная функция}%
        \index{Тьюринга машина}%
        \index{Машина!Тьюринга}%
        \glossary{Тьюринг@\Тьюринг}%
машине~Тьюринга.
        %
\end{theorem}

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

После этого остаётся только сослаться на то, что всякая функция,
вычисляемая программой с конечным числом регистров, вычислима на
машине~Тьюринга (как мы видели в разделе~\ref{chapt10-2},
теорема~\ref{program-to-turing}).
        %
\end{proof}

Поэтому если мы верим в \лк тезис~Тьюринга\пк, гласящий, что
        \index{Тьюринга тезис}%
        \index{Чёрча тезис}%
всякая вычислимая функция вычислима на машине~Тьюринга, то
должны верить и в \лк тезис~Чёрча\пк\ (всякая вычислимая функция
частично рекурсивна), так что эти тезисы равносильны.

\begin{historyremark}
        %
На самом деле история здесь сложнее и примерно может быть
описана так. Определение примитивно рекурсивной функции было
        \glossary{Гёдель@\Гедель}%
        \index{Функция!примитивно рекурсивная}%
        \index{Примитивно рекурсивная функция}%
дано великим логиком Куртом Гёделем и использовано как
техническое средство при доказательстве теоремы Гёделя о
неполноте, в начале 1930\д х годов. Он же дал определение
общерекурсивной функции (не совпадающее с приведённым нами, но
        \index{Функция!общерекурсивная}%
        \index{Общерекурсивная функция}%
эквивалентное ему). Американский логик Алонзо Чёрч сформулировал
        \glossary{Чёрч@\Черч}%
свой тезис для всюду определённых функций, предположив, что
всякая вычислимая всюду определённая функция является
        \index{Функция!вычислимая}%
        \index{Вычислимая функция}%
общерекурсивной. Затем американский математик Клини предложил
        \glossary{Клини@\Клини}%
распространить этот тезис на функции, не являющиеся всюду
определёнными.


Параллельно английский математик Тьюринг и американский
        \glossary{Тьюринг@\Тьюринг}%
        \glossary{Пост@\Пост}%
        \index{Машина!Тьюринга}%
        \index{Машина!Поста}%
        \index{Тьюринга машина}%
        \index{Поста машина}%
математик Пост предложили свои модели абстрактных вычислительных
машин (машины Тьюринга и Поста), отличающиеся лишь некоторыми
деталями, и высказали предположение о том, что такие машины
покрывают весь класс алгоритмических процессов. Вскоре стало
ясно, что вычислимость функции на таких машинах равносильна
частичной рекурсивности. (Исторические подробности можно
узнать из книги Клини~\cite{kleene}.)

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

(Заметим в скобках, что ещё одна вычислительная модель\т
        \index{Алгоритм (алгорифм) Маркова}%
\emph{нормальные алгорифмы}, или \emph{алгоритмы Маркова}, были
        \index{Нормальный алгорифм}%
предложены Андреем Андреевичем Марковым\д младшим (сыном старшего,
в честь которого названы марковские цепи и марковские процессы).
Это было уже в 1950\д ые годы.
Марков писал слово \textit{алгорифм} через \лк{\it{ф}}\пк.
Соответствующий принцип (всякий алгорифм эквивалентен
нормальному) он называл \emph{принципом нормализации}. В его
        \index{Принцип нормализации}%
        \index{Нормализации принцип}%
работах нормальные алгорифмы использовались для построения
        \index{Ассоциативное исчисление!неразрешимое}
        \index{Неразрешимое ассоциативное исчисление}
        \index{Исчисление!неразрешимое}
неразрешимого ассоциативного исчисления
(см.~раздел~\ref{chapt09-4}). Кроме того, Марков реально выписал
во всех деталях конструкцию универсального алгоритма и провёл
        \index{Универсальная функция}%
        \index{Функция!универсальная}
точное доказательство его корректности; кажется, это достижение
остаётся никем не повторённым\т ни у кого больше не хватило
настойчивости, чтобы для какого\д то языка программирования
написать на этом языке его интерпретатор и формально доказать
его корректность.)
        %
\end{historyremark}

Наше доказательство
теорем~\ref{turing-to-recursive} и~\ref{recursive-to-turing}
позволяет также получить такое следствие,
        \index{Теорема!Клини о нормальной форме}%
        \glossary{Клини@\Клини}%
называемое иногда
\emph{теоремой Клини о нормальной форме}:

\begin{theorem}
        \label{kleene-normal-form}
Всякая частично рекурсивная функция~$f$
представима в виде
        $$
f(x)=a(\mu z (b(x,z)=0)),
        $$
где $a$ и~$b$\т некоторые примитивно рекурсивные функции.
        %
\end{theorem}

\begin{proof}
        %
В самом деле, любая частично рекурсивная функция вычислима
на машине~Тьюринга, а следовательно, представима в нужном
нам виде, как видно из доказательства теоремы~\ref{turing-to-recursive}
(в качестве~$a$ берётся
функция, дающий первый член пары по её номеру).
        %
\end{proof}

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

\begin{problem}
        %
Покажите, что одним $\mu$\д оператором, применяя его последним,
не обойтись: не всякая частично рекурсивная функция представима в виде
        $$
f(x)=\mu z (b(x,z)=0)
        $$
где $b$\т некоторая примитивно рекурсивная функция.
        %
\end{problem}

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

\begin{theorem}
        \label{enumerable-primitive-projection}%
Всякое перечислимое множество есть проекция
примитивно рекурсивного множества.
        %
\end{theorem}

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

\section{Вычислимость с оракулом}\label{chapt11-7}
        \index{Вычислимость!с оракулом}%
        \index{Относительная вычислимость}%

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

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

\begin{theorem}
        \label{oracle-recursive}%
Класс~$\calF[\alpha]$ состоит из всех функций, вычислимых
с оракулом~$\alpha$ (то есть с помощью программ,
вызывающих~$\alpha$ как внешнюю процедуру).
        %
\end{theorem}

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

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

Для этого вспомним критерий относительной вычислимости, данный
нами выше в разделе~\ref{chapt07-2}
(теорема~\ref{alternative-definition-relative-computability}).
Пусть функция~$f$ вычислима относительно всюду определённой
функции~$\alpha$. Тогда, как мы знаем, существует перечислимое
множество~$W$ троек вида~$\langle x,y,t\rangle$, где $x$ и~$y$\т
        \index{Образец}%
        \index{Корректное множество}%
натуральные числа, а $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)\hm=0$ и $t$ есть часть функции~$\alpha$, а
функция~$p_1$ выделяет из номера тройки $[y,t,u]$ её первый
член~$y$.

Осталось показать, что множество~$\{ t \mid \text{образец}$ с номером~$t$
есть часть функции~$\alpha\}$ является примитивно рекурсивным
относительно~$\alpha$. При доказательстве мы будем предполагать, что нумерация
образцов такова, что следующие функции примитивно рекурсивны (они
определены для образцов с непустой областью определения; для
пустого образца доопределим их как угодно):
         %
\begin{itemize}
        %
\item $\lastx(t)$\т наибольшее из чисел, на котором
      определён образец с номером~$t$;
        %
\item $\lasty(t)$\т значение функции\д образца с номером~$t$
      в максимальной точке своей области определения;
        %
\item $\allbutlast(t)$\т номер образца, который получится
      из образца с номером~$t$, если удалить максимальную точку
      области определения.
        %
\end{itemize}

Тогда можно записать такое рекурсивное определение: образец с
номером~$t$ есть часть функции~$\alpha$, если либо этот образец пуст, либо
$\alpha(\lastx(t))\hm= \lasty(t)$ и
образец с номером~$\allbutlast(t)$ есть часть
функции~$\alpha$.

Это определение использует \лк возвратную рекурсию\пк,
которая разобрана в теореме~\ref{back-recursion} (с.~\pageref{back-recursion});
значение
функции определяется рекурсивно через её значения в меньших
точках. Надо только выбрать нумерацию образцов так, чтобы
$\allbutlast(t)$ было меньше~$t$
для всех~$t$. Этого
несложно добиться: например, можно нумеровать образцы с помощью
простых чисел, считая, что образец~$\{\langle a,b
\rangle,\dots,\langle e,f\rangle\}$ имеет номер
$p_a^{(b+1)}\ldots p_e^{(f+1)}$, где $p_i$\т простое
число с номером~$i$ (так что $p_0\hm=2$, $p_1\hm=3$, $p_2\hm=5$,\,$\dots$).
        %
\end{proof}

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

\section[Оценки скорости роста. Функция~Аккермана]
        {Оценки скорости роста.\\ Функция~Аккермана}\label{chapt11-8}

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

\begin{theorem}
        \label{universal-primitive-recursive-1}%
        \index{Универсальная функция}%
        \index{Функция!универсальная}%
Существует всюду определённая вычислимая функция двух аргументов,
универсальная для класса всех примитивно рекурсивных функций
одного аргумента.
        %
\end{theorem}

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

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

Однако интересно указать и более конкретную причину, мешающую
некоторым вычислимым функциям быть примитивно рекурсивными. Вот
одна из возможностей: примитивно рекурсивные функции не могут
быстро расти. Эта идея восходит к~Аккерману, который построил
функцию, растущую быстрее всех примитивно рекурсивных\т
        \glossary{Аккерман@\Аккерман}%
        \index{Аккермана функция}%
        \index{Функция!Аккермана}%
\emph{функцию~Аккермана}. Сейчас мы изложим эту конструкцию
(хотя детали построения будут иными).

Определим последовательность функций $\alpha_0,\alpha_1,\dots$
от одного аргумента. (Все эти функции будут всюду определёнными.)
Положим~$\alpha_0(x)\hm=x\hm+1$. Определяя~$\alpha_i$, мы будем
использовать такое обозначение: $f^{[n]}(x)$~означает~$f(f(\ldots f(x)\ldots))$,
где функция~$f$ использована $n$~раз. Так вот,
        $$
\alpha_{i} (x) = \alpha_{i-1}^{[x+2]}(x)
        $$
(почему удобно применять функцию~$\alpha_{i-1}$ ровно $x\hm+2$~раза,
мы увидим чуть позже).

Очевидные свойства (формально их можно доказать по индукции):
        %
\begin{itemize}
        %
\item $\alpha_i (x)\hm>x$ при всех~$i$ и~$x$;
        %
\item $\alpha_i (x)$~возрастает с возрастанием~$x$;
        %
\item $\alpha_i (x)$~возрастает с возрастанием~$i$ (для каждого
     фиксированного~$x$);
        %
\item $\alpha_{i} (x) \ge \alpha_{i-1}(\alpha_{i-1}(x))$.
        %
\end{itemize}

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

\begin{theorem}
        \label{akkerman-bound}%
Пусть $f$\т примитивно рекурсивная функция $n$~аргументов.
Тогда найдётся такое~$k$, что
        $$
f(x_1,\dots,x_n) \le \alpha_k (\max(x_1,\dots,x_n))
        $$
при всех~$x_1,\dots,x_n$.
        %
\end{theorem}

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

Для базисных функций утверждение очевидно. Посмотрим на
подстановку. Пусть
        $$
f(x)=g(h_1(x),\dots,h_k(x))
        $$
(для краткости мы пишем одну букву~$x$, имея в виду вектор
переменных). Пусть $\alpha_N$~оценивает все функции~$h_1,\dots,h_k$
и функцию~$g$ сверху, то есть~$h_i(x)\hm\le
\alpha_N(\max(x))$ при всех~$i$ и~$x$, а также $g(y)\hm\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$ определяется рекурсивно:
        %
\begin{align*}
f(x,0)&=g(x);\\
f(x,n+1)&=h(x,n,f(x,n)).
        %
\end{align*}
        %
(Здесь $x$~также обозначает набор нескольких переменных.) Пусть
функции~$g$ и~$h$ оцениваются сверху функцией~$\alpha_N$. Тогда
\begin{multline*}
f(x,1)=h(x,0,f(x,0))\le \alpha_N(\max(x,0,f(x,0)))\le\\
\le
                \alpha_N(\max(x,0,\alpha_N(\max(x)))) \le
                \alpha_N(\alpha_N(\max(x)))
\end{multline*}
(в последнем переходе
мы пользуемся тем, что~$\alpha_N(t)\hm>t$).
Аналогично $f(x,2)\hm\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))),
        $$
что и требовалось доказать.
        %
\end{proof}

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

Очевидным следствием полученной оценки является такое утверждение:
        %
\begin{theorem}
        \label{akkerman-function}
Функция~$A(n)\hm=\alpha_n(n)$ растёт быстрее любой примитивно
рекурсивной функции.
        %
\end{theorem}

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

\begin{problem}
        %
Покажите, что прямой пересчёт (в возрастающем порядке)
бесконечного примитивно рекурсивного множества может не
быть примитивно рекурсивным.
        %
\end{problem}

\begin{problem}
        %
Покажите, что функция, обратная к примитивно рекурсивной
биекции $i\colon \bbN \hm \to \bbN$, может не быть
примитивно рекурсивной.
        %
\end{problem}
