Частично рекурсивные функции¶

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

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

Формально частично рекурсивные функции определяются на множестве натуральных чисел \(\mathbb{N}\) (включая ноль). Исходными (базисными) функциями считаются:

• Нулевая функция \(O(x) = 0\) для любого \(x\).
• Функция следования \(S(x) = x + 1\).
• Функции проекции \(I_i^n(x_1, \dots, x_n) = x_i\) для \(1 \le i \le n\).

Из этих базисных функций новые функции строятся с помощью трёх операторов:

1. Суперпозиция (подстановка) — подстановка значений одних функций в аргументы другой.
2. Примитивная рекурсия — определение функции \(f\) через рекуррентные соотношения: \(f(0, \vec{y}) = g(\vec{y})\) и \(f(x+1, \vec{y}) = h(x, f(x, \vec{y}), \vec{y})\), где \(g\) и \(h\) — уже построенные функции.
3. Минимизация (оператор наименьшего числа) — для функции \(g(x, \vec{y})\) определяется \(f(\vec{y}) = \mu x [g(x, \vec{y}) = 0]\), где \(\mu x\) означает наименьшее \(x\), при котором \(g(x, \vec{y}) = 0\). Если такого \(x\) не существует, то \(f(\vec{y})\) считается неопределённым.

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

¶Отличие от примитивно рекурсивных функций

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

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

¶Связь с вычислимостью

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

Этот результат является фундаментальным для теории алгоритмов: он показывает, что понятие алгоритмической вычислимости не зависит от конкретной модели вычислений, а частично рекурсивные функции дают математически строгое определение этого понятия.

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

¶Функция, не являющаяся примитивно рекурсивной

Классический пример — функция Аккермана \(A(m, n)\), которая растёт быстрее любой примитивно рекурсивной функции. Она определяется рекурсивно:

\[ A(0, n) = n + 1, \quad A(m+1, 0) = A(m, 1), \quad A(m+1, n+1) = A(m, A(m+1, n)). \]

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

¶Функция с неопределённостью

Рассмотрим функцию \(f(x) = \mu y [y = x]\). Она определена для любого \(x\) и равна \(x\). Но если взять \(g(x) = \mu y [y > x]\), то для любого \(x\) существует \(y = x+1\), так что функция всюду определена. Однако оператор минимизации может дать неопределённость, если условие никогда не выполняется. Например, \(h(x) = \mu y [y < 0]\) не определена ни для какого \(x\), так как натуральных чисел меньше нуля не существует.

¶История и развитие

Понятие рекурсивных функций восходит к работам Гёделя (1931), который использовал примитивно рекурсивные функции для доказательства теорем о неполноте. В 1930-х годах Алонзо Чёрч, Стивен Клини и Эмиль Пост независимо разработали формальные системы, эквивалентные по вычислительной мощности. Чёрч ввёл понятие λ-определимых функций, Клини — частично рекурсивных функций. В 1936 году Алан Тьюринг предложил модель машины Тьюринга, и вскоре было доказано, что все эти формализмы эквивалентны. Тезис Чёрча — Тьюринга, утверждающий, что любая интуитивно вычислимая функция является частично рекурсивной, стал краеугольным камнем теории алгоритмов.

¶Значение в информатике и математике

• Теория алгоритмов: частично рекурсивные функции служат математической моделью алгоритмов. Они позволяют строго доказывать неразрешимость задач (например, проблема остановки).
• Теория сложности вычислений: классы рекурсивных функций (примитивно рекурсивные, частично рекурсивные, рекурсивные перечислимые множества) лежат в основе классификации задач по сложности.
• Формальные языки и грамматики: рекурсивные функции используются для описания синтаксиса и семантики языков программирования.
• Математическая логика: рекурсивные функции применяются в доказательствах теорем о неполноте, в теории моделей и в теории множеств.

¶Критика и ограничения

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

¶Интересные факты

• Частично рекурсивные функции образуют счётное множество, в то время как множество всех функций из \(\mathbb{N}\) в \(\mathbb{N}\) несчётно. Это означает, что подавляющее большинство функций не являются вычислимыми.
• Существует универсальная частично рекурсивная функция (нумерация Клини), которая может имитировать любую другую частично рекурсивную функцию. Это аналог универсальной машины Тьюринга.
• Проблема остановки для частично рекурсивных функций неразрешима: не существует алгоритма, который бы для любой частично рекурсивной функции и любых входных данных определял, определена ли она на них.

¶Источники

• Клини С. К. Введение в метаматематику. — М.: Издательство иностранной литературы, 1957.
• Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.: Мир, 1972.
• Мальцев А. И. Алгоритмы и рекурсивные функции. — М.: Наука, 1965.
• Успенский В. А., Семёнов А. Л. Теория алгоритмов: основные открытия и приложения. — М.: Наука, 1987.
• Тьюринг А. М. О вычислимых числах с приложением к проблеме разрешимости // Математические основы теории вычислимости. — М.: Мир, 1970.