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

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

К ним относятся нулевая функция $O(x) = 0$, возвращающая ноль для любого аргумента, функция следования $S(x) = x + 1$, увеличивающая число на единицу, и функция проекции $I_n^k(x_1, \dots, x_n) = x_k$, выбирающая $k$-й аргумент из набора.

Разбор по случаям

Примеры

Вычисление константы 2. Чтобы построить функцию $f(x) = 2$, используем базовые примитивно рекурсивные функции и операцию суперпозиции. Сначала применительно к аргументу $x$ берём нуль-функцию $O(x) = 0$. Затем последовательно применяем функцию следования: $S(O(x)) = 1$, а повторное применение дает $S(S(O(x))) = 2$. Таким образом, комбинация функций следования и нуля дает нужную постоянную величину.

Выделение второго аргумента. Рассмотрим выбор элемента из набора трех переменных $(x_1, x_2, x_3) = (5, 9, 2)$.

Применяется функция проекции $I_3^2(x_1, x_2, x_3)$, где верхний индекс указывает номер выбираемого аргумента, а нижний — общее количество переменных. Подставляя значения, получаем $I_3^2(5, 9, 2) = 9$. Это демонстрирует, как работают простейшие примитивно рекурсивные функции селекции.

Сложение двух чисел через примитивную рекурсию. Построим схему вычисления функции сложения двух аргументов $f(x, y) = x + y$ с помощью оператора примитивной рекурсии. Базовый шаг задает значение при нулевом втором аргументе: $f(x, 0) = I_1^1(x) = x$, где начальная функция $g(x) = I_1^1(x)$ вычисляет проекцию. Шаг перехода задает значение для $y + 1$ через предыдущий результат: $f(x, y + 1) = S(f(x, y))$.

Для этого используется вспомогательная функция $h(x, y, z) = S(I_3^3(x, y, z))$, где третьему аргументу $z$ соответствует результат $f(x, y)$.

Вычислим значение для $x = 2$ и $y = 2$: сначала $f(2, 0) = 2$, затем $f(2, 1) = S(f(2, 0)) = 3$ и наконец $f(2, 2) = S(f(2, 1)) = 4$. Данная конструктивная схема явно доказывает примитивную рекурсивность операции сложения.

Частые ошибки

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

Коротко

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