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

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

Определение

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

К числу исходных примитивно рекурсивных функций относятся функции следующих трёх видов:

• Нулевая функция $O$ одного переменного, сопоставляющая любому натуральному числу значение 0.
• Функция следования $S$ одного переменного, сопоставляющая любому натуральному числу $x$ непосредственно следующее за ним натуральное число $x + 1$.
• Функции $I_{n}^{m}$, где $0<m\leqslant n$, от n переменных, сопоставляющие любому упорядоченному набору $x_{1},...x_{n}$ натуральных чисел число $x_m$ из этого набора.

Операторы подстановки и примитивной рекурсии определяются следующим образом:

• Пусть f — примитивно рекурсивная функция от m переменных, а g₁,... g_m — упорядоченный набор примитивно рекурсивных функций от n переменных каждая. Тогда результатом подстановки функций g_k в функцию f называется функция h от n переменных, сопоставляющая любому упорядоченному набору $x_{1},...x_{n}$ натуральных чисел число

$h(x_{1},\ldots \,x_{n})=f(g_{1}(x_{1},\ldots \,x_{n}),\ldots \,g_{m}(x_{1},\ldots \,x_{n}))$.

• Пусть f — примитивно рекурсивная функция от n переменных, а g — примитивно рекурсивная функция от n+2 переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций f и g называется функция h от n+1 переменной вида

$h(x_{1},\ldots \,x_{n},0)=f(x_{1},\ldots \,x_{n})$;

$h(x_{1},\ldots \,x_{n},y+1)=g(x_{1},\ldots \,x_{n},y,h(x_{1},\ldots x_{n},y))$.

Примеры

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

• Сложение двух натуральных чисел может быть рассмотрено в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям $I_{1}^{1}$ и f, вторая из которых получается подстановкой основной функции $I_{3}^{3}$ в основную функцию $S$:

$+(x,0)=x$;

$+(x,y+1)=f(x,y,+(x,y))$;

$f(x,y,z)=S(I_{3}^{3}(x,y,z))$.

• Умножение двух натуральных чисел может быть рассмотрено в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям $O$ и f, вторая из которых получается подстановкой основных функций $I_{3}^{1}$ и $I_{3}^{3}$ в функцию сложения:

$\times (x,0)=O(x)$;

$\times (x,y+1)=f(x,y,\times (x,y))$;

$f(x,y,z)=+(I_{3}^{1}(x,y,z),I_{3}^{3}(x,y,z))$.

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

$-(x,y)=+({-}_{1}(x,y),{-}_{2}(x,y))$;

${-}_{2}(x,y)={-}_{1}(I_{2}^{2}(x,y),I_{2}^{1}(x,y))$;

$\left\{{\begin{array}{l}{-}_{1}(x,0)=I_{1}^{1}(x)\\{-}_{1}(x,y+1)=f(x,y,{-}_{1}(x,y))\end{array}}\right.$;

$f(x,y,z)=p(I_{3}^{3}(x,y,z))$;

$\left\{{\begin{array}{l}p(0)=0\\p(y+1)=I_{2}^{1}(y,p(y))\end{array}}\right.$;

Границы понятия

Любая примитивно рекурсивная функция является общерекурсивной, т. е. принимающей некоторое значение на любом отвечающем числу аргументов функции наборе натуральных чисел. Соответственно, рекурсивные функции, не являющиеся общерекурсивными, заведомо не относятся к числу примитивно рекурсивных функций. Известны также и общерекурсивные функции, не являющиеся примитивно рекурсивными. Стандартным примером здесь является функция Аккермана.

Следует, однако, заметить, что произвольная рекурсивная функция от n  переменных может быть получена из примитивно рекурсивной функции от n+1 переменной применением оператора минимизации.

Литература

• Гильберт Д, Бернайс П. Основания математики, Т. 1. — М.: Наука, 1979.
• Клини С. К. Введение в метаматематику. — М., 1957.
• Петер Р. Рекурсивные функции — ИЛ, 1954.

cs:Primitivně rekurzivní funkce he:פונקציה פרימיטיבית רקורסיבית