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

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

Определение и формальная система

Класс примитивно рекурсивных функций определяется индуктивно. Сначала задаются базовые функции:

1. Нулевая функция \(Z(x) = 0\) для любого \(x \in \mathbb{N}\).
2. Функция следования \(S(x) = x + 1\).
3. Функции проекции \(P_i^n(x_1, \dots, x_n) = x_i\) для \(1 \le i \le n\).

Затем определяются операторы, которые позволяют строить новые функции из уже имеющихся:

1. Оператор суперпозиции (подстановки): Пусть задана функция \(f\) от \(m\) аргументов и функции \(g_1, \dots, g_m\) от \(n\) аргументов. Тогда функция \(h\) от \(n\) аргументов, определяемая как \(h(x_1, \dots, x_n) = f(g_1(x_1, \dots, x_n), \dots, g_m(x_1, \dots, x_n))\), является примитивно рекурсивной, если \(f\) и все \(g_i\) примитивно рекурсивны.
2. Оператор примитивной рекурсии: Пусть задана функция \(g\) от \(n\) аргументов и функция \(h\) от \(n+2\) аргументов. Тогда функция \(f\) от \(n+1\) аргумента определяется рекурсивно:

• \(f(x_1, \dots, x_n, 0) = g(x_1, \dots, x_n)\)
• \(f(x_1, \dots, x_n, y+1) = h(x_1, \dots, x_n, y, f(x_1, \dots, x_n, y))\)

Функция \(f\) называется примитивно рекурсивной, если \(g\) и \(h\) примитивно рекурсивны.

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

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

Большинство элементарных арифметических функций являются примитивно рекурсивными. Приведём некоторые из них с формальными определениями.

Сложение

\(Add(x, 0) = x\) \(Add(x, y+1) = S(Add(x, y))\)

Здесь \(g(x) = P_1^1(x) = x\), а \(h(x, y, z) = S(P_3^3(x, y, z)) = S(z)\).

Умножение

\(Mul(x, 0) = 0\) \(Mul(x, y+1) = Add(x, Mul(x, y))\)

Возведение в степень

\(Pow(x, 0) = 1\) (функция-константа, которая также примитивно рекурсивна) \(Pow(x, y+1) = Mul(x, Pow(x, y))\)

Функция предшествования (для натуральных чисел)

\(Pred(0) = 0\) \(Pred(y+1) = y\)

Усечённое вычитание (разность до нуля)

\(Sub(x, 0) = x\) \(Sub(x, y+1) = Pred(Sub(x, y))\)

Эта функция возвращает \(x - y\), если \(x \ge y\), и 0 в противном случае. На её основе можно определить другие арифметические предикаты.

Факториал

\(Fac(0) = 1\) \(Fac(y+1) = Mul(S(y), Fac(y))\)

Константные функции

Функция, возвращающая константу \(k\) для любого аргумента, примитивно рекурсивна. Например, \(Const_2(x) = S(S(Z(x)))\).

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

Класс примитивно рекурсивных функций обладает рядом важных свойств:

• Замкнутость относительно операций: Класс замкнут относительно суперпозиции и примитивной рекурсии (по определению). Кроме того, он замкнут относительно многих других операций, таких как ограниченная минимизация (поиск наименьшего \(y\), меньшего заданного числа, такого, что \(P(x,y)\) истинно, где \(P\) — примитивно рекурсивный предикат).
• Разрешимость: Предикаты (функции, принимающие значения 0 или 1), соответствующие примитивно рекурсивным функциям, образуют класс примитивно рекурсивных предикатов. Для любого такого предиката существует алгоритм, проверяющий его истинность для заданных аргументов, и этот алгоритм всегда останавливается.
• Выразительность в формальной арифметике: Все примитивно рекурсивные функции могут быть представлены (кодированы) в формальной арифметике Пеано. Это свойство используется при доказательстве неполноты формальных систем.
• Неполнота класса: Существуют вычислимые (общерекурсивные) функции, которые не являются примитивно рекурсивными. Классическим примером является функция Аккермана, которая растёт быстрее любой примитивно рекурсивной функции. Другой пример — функция, вычисляющая \(n\)-е простое число (хотя она и является общерекурсивной, её рекурсивное определение выходит за рамки примитивной рекурсии).

Связь с другими классами функций

Примитивно рекурсивные функции занимают промежуточное положение между более узкими и более широкими классами вычислимых функций:

• Элементарные функции (по Кальмару) — это подкласс примитивно рекурсивных функций, которые могут быть построены с помощью ограниченного набора операций (суперпозиция, ограниченная сумма и ограниченное произведение). Все элементарные функции примитивно рекурсивны, но не наоборот.
• Общерекурсивные функции — это класс всех вычислимых функций, определённых для всех натуральных чисел. Примитивно рекурсивные функции являются подклассом общерекурсивных. Отличие заключается в том, что для общерекурсивных функций допускается оператор неограниченной минимизации (поиск наименьшего \(y\) без верхней границы), который может приводить к неопределённости (зацикливанию) для некоторых аргументов, если искомого \(y\) не существует.
• Частично рекурсивные функции — это самый широкий класс вычислимых функций, которые могут быть не определены для некоторых аргументов. Примитивно рекурсивные функции всегда всюду определены (тотальны), поэтому они являются подклассом частично рекурсивных функций.

Применение и значение

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

• Теория алгоритмов: Она служит одним из первых и наиболее интуитивно понятных способов формализации понятия алгоритма. Хотя она не охватывает все алгоритмы, она позволяет строго определить, что значит «вычислить» функцию, используя только простые рекурсивные шаги.
• Теория вычислимости: Примитивно рекурсивные функции используются для доказательства теорем о неразрешимости и неполноте (например, теоремы Гёделя о неполноте). Кодирование формул и доказательств в арифметике часто осуществляется с помощью примитивно рекурсивных функций.
• Математическая логика: В формальных системах, таких как арифметика Пеано, все примитивно рекурсивные функции могут быть явно определены. Это позволяет формулировать в языке арифметики утверждения о вычислимых процессах.
• Информатика: Понятие примитивной рекурсии лежит в основе многих языков программирования, особенно в функциональном программировании и в доказательстве корректности программ. Рекурсивные определения, используемые в языках типа Haskell или ML, часто являются частным случаем примитивной рекурсии. Кроме того, класс примитивно рекурсивных функций используется в теории сложности вычислений для определения классов сложности, таких как EXP (экспоненциальное время).

Ограничения и критика

Основное ограничение класса примитивно рекурсивных функций — его неполнота. Как уже упоминалось, существуют простые и естественные вычислимые функции, такие как функция Аккермана, которые не являются примитивно рекурсивными. Это означает, что формализм примитивной рекурсии не охватывает всех возможных алгоритмов.

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

Источники

1. Мендельсон, Э. «Введение в математическую логику». — М.: Наука, 1976.
2. Клини, С. К. «Введение в метаматематику». — М.: Издательство иностранной литературы, 1957.
3. Успенский, В. А., Семёнов, А. Л. «Теория алгоритмов: основные открытия и приложения». — М.: Наука, 1987.
4. Роджерс, Х. «Теория рекурсивных функций и эффективная вычислимость». — М.: Мир, 1972.