Примитивно рекурсивные функции: база и операторы

Примитивно рекурсивные функции - это фундамент теории вычислимости: класс функций, которые можно построить из трёх простейших «кирпичей» с помощью всего двух правил сборки. Идея появилась в работах Гёделя, Сколема и Аккермана как попытка точно очертить, что значит «эффективно вычислимая функция». Класс получился настолько естественным, что покрывает почти всю школьную и большую часть вузовской арифметики, но при этом оставляет за бортом несколько важных функций. Ниже разберём базис, операторы, классические примеры построения и границу класса. Если нужно построить конкретную функцию по шагам, удобнее сразу собрать запрос в инструменте.

Зачем нужен этот класс

Когда математики формализовали понятие алгоритма, потребовался язык, на котором любую «механически считаемую» функцию можно выписать явно, без отсылок к интуиции. Примитивно рекурсивные функции стали первым таким языком. Их ценность в том, что каждая функция класса заведомо всюду определена (тотальна) и заведомо вычислима: само определение содержит рецепт расчёта.

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

Базисные функции

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

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

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

Рассчитать для своей задачи

Оператор суперпозиции

Первый способ строить новые функции из старых - суперпозиция (подстановка). Если есть функция $g$ от $m$ аргументов и функции $h_1, \dots, h_m$ от $n$ аргументов каждая, то их композиция

$$f(x_1, \dots, x_n) = g\bigl(h_1(\bar{x}), \dots, h_m(\bar{x})\bigr)$$

тоже принадлежит классу. Проще говоря, результаты одних функций подставляются на места аргументов другой. Так из $S$ и проекций уже можно получить, скажем, функцию $x + 3$, трижды применив следование.

Суперпозиция отвечает за «горизонтальную» сборку: соединение готовых блоков в цепочку без всякого цикла.

Оператор примитивной рекурсии

Главный инструмент класса - схема примитивной рекурсии. Она задаёт функцию через два равенства: значение в нуле и переход от $y$ к $y+1$.

$$\begin{aligned} f(\bar{x}, 0) &= g(\bar{x}) \\ f(\bar{x}, y+1) &= h\bigl(\bar{x}, y, f(\bar{x}, y)\bigr) \end{aligned}$$

Здесь $g$ задаёт базу рекурсии, а $h$ - шаг: как из уже посчитанного значения $f(\bar{x}, y)$ получить следующее. Если $g$ и $h$ уже примитивно рекурсивны, то и $f$ примитивно рекурсивна. Ключевая особенность: число шагов рекурсии ограничено заранее значением $y$, поэтому процесс гарантированно конечен - никаких бесконечных циклов.

Именно ограниченность глубины отличает примитивную рекурсию от общей. В цикле языка программирования это аналог for с известной заранее границей, а не while с неизвестным условием выхода.

Рассчитать для своей задачи

Пример: сложение

Покажем, как сложение строится по схеме. Зафиксируем первый аргумент $x$ и ведём рекурсию по второму:

$$\begin{aligned} x + 0 &= x \\ x + (y+1) &= (x + y) + 1 \end{aligned}$$

В терминах операторов: база $g(x) = x$ - это проекция $I^1_1$, а шаг $h(x, y, z) = z + 1$ - это суперпозиция следования $S$ с проекцией, выбирающей предыдущее значение суммы $z = x + y$. Обе составляющие примитивно рекурсивны, значит, и сложение примитивно рекурсивно.

Пример: умножение и дальше

Когда сложение определено, умножение строится через него той же схемой:

$$\begin{aligned} x \cdot 0 &= 0 \\ x \cdot (y+1) &= x \cdot y + x \end{aligned}$$

База - нуль-функция, шаг - сложение уже посчитанного произведения с $x$. По той же логике дальше идут возведение в степень $x^y$, факториал $n!$, предшественник, усечённое вычитание, остаток от деления, минимум, максимум. Практически вся школьная арифметика и почти вся комбинаторика лежат внутри класса. Тот же принцип «сначала проще, потом сложнее из проще» работает и в недетерминированной машине Тьюринга, где вычисление тоже описывается через переходы между состояниями.

Чего в классе нет: функция Аккермана

Соблазнительно решить, что примитивно рекурсивны вообще все вычислимые тотальные функции. Это не так. Классический контрпример - функция Аккермана $A(m, n)$. Она всюду определена и вычислима, но растёт быстрее любой примитивно рекурсивной функции: для каждой примитивно рекурсивной $f$ найдётся точка, после которой $A$ её обгоняет.

$$\begin{aligned} A(0, n) &= n + 1 \\ A(m+1, 0) &= A(m, 1) \\ A(m+1, n+1) &= A\bigl(m, A(m+1, n)\bigr) \end{aligned}$$

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

Рассчитать для своей задачи

Связь с другими классами

Примитивно рекурсивные функции вкладываются в более широкие классы строго:

• Примитивно рекурсивные $\subsetneq$ общерекурсивные (тотальные вычислимые). Различие даёт функция Аккермана.
• Общерекурсивные $\subsetneq$ частично рекурсивные - последние могут быть не всюду определены, тут уже работает оператор минимизации $\mu$ (поиск наименьшего $y$ с заданным свойством, который может не найтись).
• По тезису Чёрча - Тьюринга частично рекурсивные функции совпадают с вычислимыми на машине Тьюринга.

Так выстраивается лестница: от заведомо тотальных и «безопасных» примитивно рекурсивных функций до полного класса всего вычислимого.

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

• Путают примитивную рекурсию с обычной рекурсией из программирования. В программировании рекурсия может не завершиться. Примитивная рекурсия по определению ограничена счётчиком и всегда конечна.
• Считают, что класс покрывает все вычислимые функции. Нет: функция Аккермана вычислима и тотальна, но в класс не входит.
• Забывают про проекции в базисе. Без функций-проекций нельзя корректно «выбирать» нужный аргумент в многоместных функциях, и схема рекурсии не собирается.
• Смешивают оператор суперпозиции и оператор примитивной рекурсии. Суперпозиция - это подстановка без цикла, рекурсия - построение по шагам от нуля.
• Думают, что оператор минимизации тоже примитивно рекурсивен. Минимизация $\mu$ выводит за пределы класса именно потому, что поиск может не завершиться.

FAQ

Чем примитивно рекурсивная функция отличается от общерекурсивной? Примитивно рекурсивная строится только из базиса с помощью суперпозиции и примитивной рекурсии и всегда тотальна с заранее ограниченной глубиной вычисления. Общерекурсивные функции дополнительно используют оператор минимизации и включают функции вроде Аккермана, которые растут слишком быстро для примитивной рекурсии.

Является ли функция Аккермана вычислимой? Да, она всюду определена и её можно вычислить алгоритмом. Просто она не примитивно рекурсивна: её рост превосходит любую функцию класса, потому что вложенность рекурсии не ограничивается одной переменной.

Все ли арифметические функции примитивно рекурсивны? Практически вся повседневная арифметика - сложение, умножение, степень, факториал, деление с остатком, НОД - примитивно рекурсивна. Выходят за класс лишь специально сконструированные быстрорастущие функции вроде Аккермана и функции, требующие неограниченного поиска.

Коротко

Примитивно рекурсивные функции - это класс, собираемый из трёх базисных функций (нуль, следование, проекции) двумя операторами: суперпозицией и примитивной рекурсией. Каждая такая функция всюду определена и вычислима за конечное число шагов, так как глубина рекурсии ограничена заранее. Сложение, умножение, степень, факториал строятся внутри класса по простой схеме «база плюс шаг». Граница класса проходит по функции Аккермана: она вычислима и тотальна, но растёт быстрее любой примитивно рекурсивной функции и требует более широкого класса общерекурсивных функций с оператором минимизации.