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

Примити́вно рекурси́вная фу́нкция, функция от натуральных аргументов с натуральными значениями, которую можно получить из простейших функций

${\displaystyle s(x)=x+1,\quad o(x)=0,\quad I_{m}^{n}\left(x_{1},\ldots ,x_{n}\right)=x_{m}}$

конечным числом операций суперпозиции и примитивной рекурсии.

Поскольку исходные функции являются вычислимыми, а операторы суперпозиции и примитивной рекурсии вычислимость сохраняют, множество всех примитивно рекурсивных функций есть подкласс класса всех вычислимых функций. Каждая примитивно рекурсивная функция задаётся описанием её построения из исходных функций (примитивно рекурсивное описание), и, следовательно, класс всех примитивно рекурсивных функций счётен. Практически все арифметические функции, употребляемые в математике по конкретным поводам, являются примитивно рекурсивными функциями, например: ${\displaystyle x+y}$, ${\displaystyle x\cdot y}$, ${\displaystyle x^{y}}$, ${\displaystyle \mathrm {sg} (x)}$, ${\displaystyle \left[{\frac {x}{y}}\right]}$, остаток от деления ${\displaystyle x}$ на ${\displaystyle y}$, ${\displaystyle \pi (x)}$ – простое число с номером ${\displaystyle x}$ и т. д.

Отношение ${\displaystyle P\left(x_{1},\ldots ,x_{n}\right)}$ на натуральных числах называется примитивно рекурсивным отношением (п. р. о.), если функция ${\displaystyle g\left(x_{1},\ldots ,x_{n}\right)}$, равная ${\displaystyle 1}$, когда ${\displaystyle P\left(x_{1},\ldots ,x_{n}\right)}$ истинно, и ${\displaystyle 0}$ , когда ${\displaystyle P\left(x_{1},\ldots ,x_{n}\right)}$ ложно, является примитивно рекурсивной функцией. Говорят, что отношение ${\displaystyle P\left(x_{1},\ldots ,x_{n},z\right)}$ получено из отношения ${\displaystyle Q\left(x_{1},\ldots ,x_{n},y,z\right)}$ c помощью ограниченного квантора, если

${\displaystyle P\left(x_{1},\ldots ,x_{n},z\right)\Leftrightarrow \forall y\left(y\leqslant z\Rightarrow Q\left(x_{1},\ldots ,x_{n},y,z\right)\right)}$

или

${\displaystyle P\left(x_{1},\ldots ,x_{n},z\right)\Leftrightarrow \exists y\left(y\leqslant z\&Q\left(x_{1},\ldots ,x_{n},y,z\right)\right){\text{. }}}$

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

Пусть ${\displaystyle f_{1},\ldots ,f_{s+1}}$ суть ${\displaystyle n}$-местные примитивно рекурсивные функции, а ${\displaystyle P_{1},\ldots ,P_{s}}$ – такие примитивно рекурсивные функции, что на любом наборе значений аргументов истинно не более одного из них. Тогда функция

${\displaystyle f\left(x_{1},\ldots ,x_{n}\right)=\left\{{\begin{aligned}&f_{1}\left(x_{1},\ldots ,x_{n}\right),{\text{ если }}P_{1}\left(x_{1},\ldots ,x_{n}\right),\\&\qquad \ldots \qquad \ldots \qquad \ldots \qquad \ldots \\&f_{s}\left(x_{1},\ldots ,x_{n}\right),{\text{ если }}P_{s}\left(x_{1},\ldots ,x_{n}\right),\\&f_{s+1}\left(x_{1},\ldots ,x_{n}\right),{\text{ в других случаях }}\end{aligned}}\right.}$

является примитивно рекурсивной функцией.

Говорят, что функция ${\displaystyle f\left(x_{1},\ldots ,x_{n},z\right)}$ получена из всюду определённой функции ${\displaystyle g\left(x_{1},\ldots ,x_{n},y,z\right)}$ применением ограниченного оператора минимизации, если ${\displaystyle f\left(x_{1},\ldots ,x_{n},z\right)}$ равно минимальному ${\displaystyle y}$ такому, что ${\displaystyle y\leqslant z}$ и ${\displaystyle g\left(x_{1},\ldots ,x_{n},y,z\right)=0}$, и равно ${\displaystyle z+1}$, если такого ${\displaystyle y}$ нет. Класс примитивно рекурсивных функций замкнут относительно применения ограниченных операторов минимизации.

Функция ${\displaystyle \Phi \left(y,x_{1},\ldots ,x_{n}\right)}$ называется универсальной для класса всех ${\displaystyle n}$-местных примитивно рекурсивных функций, если для каждой примитивно рекурсивной функции ${\displaystyle f\left(x_{1},\ldots ,x_{n}\right)}$ найдётся натуральное число ${\displaystyle k}$ такое, что

${\displaystyle f\left(x_{1},\ldots ,x_{n}\right)=\Phi \left(k,x_{1},\ldots ,x_{n}\right)}$.

Для каждого ${\displaystyle n\geqslant 1}$ такая универсальная функция существует, но она не может быть примитивно рекурсивной функцией.

Всякое рекурсивно перечислимое множество есть область значений примитивно рекурсивной функции; всякое рекурсивно перечислимое отношение ${\displaystyle R\left(x_{1},\ldots ,x_{n}\right)}$ представимо в виде ${\displaystyle \exists yA\left(y,x_{1},\ldots ,x_{n}\right)}$, где ${\displaystyle A}$ – примитивно рекурсивная функция. Всякая примитивно рекурсивная функция представима в формальной арифметике, т. е. для каждой примитивно рекурсивной функции ${\displaystyle f\left(x_{1},\ldots ,x_{n}\right)}$ найдётся арифметическая формула ${\displaystyle F\left(y,x_{1},\ldots ,x_{n}\right)}$ такая, что для натуральных ${\displaystyle k_{1},\ldots ,k_{n}}$, ${\displaystyle m}$ при ${\displaystyle f\left(k_{1},\ldots ,k_{n}\right)=m}$ в формальной арифметике выводима формула ${\displaystyle F\left({\overline {m}},{\overline {k}}_{1},\ldots ,{\overline {k}}_{n}\right)}$, а при ${\displaystyle f\left(k_{1},\ldots ,k_{n}\right)\neq m}$ выводима ${\displaystyle \rceil F\left({\overline {m}},{\overline {k}}_{1},\ldots ,{\overline {k}}_{n}\right)}$ (здесь ${\displaystyle {\overline {k}}_{1},\ldots ,{\overline {k}}_{n},{\overline {m}}}$ – арифметические термы, изображающие в формальной арифметике натуральные числа ${\displaystyle k_{1},\ldots ,k_{n},m}$). Этот факт занимает центральное место в доказательстве неполноты формальной арифметики (Мендельсон. 2010^[1]).