Примитивно рекурсивные функции

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

Пусть имеется k -местная функция f и k штук n -местных функций g₁,...,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₁,...,g_k с помощью операции подстановки.

Другая операция, называемая операцией рекурсии, или примитивной рекурсии, применяется к k -местной функции f и (k+2) -местной функции g. Ее результатом будет (k+1) -местная функция h, определяемая так:

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

В последовательности h(x₁,...,x_n,0),h(x₁,...,x_n,1),... каждое значение определяется через предыдущее, поэтому если какое-то из значений не определено, то не определены и все последующие.

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

Примитивно рекурсивными называют функции, которые можно получить с помощью операций подстановки и рекурсии из следующих базисных функций: константы 0, операции прибавления единицы s : x \[ \mapsto \] x+1 и семейства функций проекции: это семейство для каждого k содержит k штук k -местных функций \[ \pi _{k}^{i}(x_{1},\dots ,x_{k})=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 и т.д.

Примеры примитивно рекурсивных функций

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

Сложение. Функция \[ \langle x,y\rangle \mapsto sum(x,y)\hm= x\hm+y \] получается с помощью рекурсии:

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

Надо, конечно, представить правую часть второго равенства как результат подстановки. Формально говоря, h(x,y,z) в определении рекурсии надо положить равным s(z), где s функция прибавления единицы.

Умножение. Функция \[ \langle x,y\rangle \mapsto prod(x,y)\hm= xy \] получается с помощью рекурсии (с использованием сложения):

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

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

Усеченное вычитание. Мы говорим об " усеченном вычитании" \[ 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*} \]