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

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

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

Формально, частично рекурсивная функция определяется как функция \( f: \mathbb{N}^k \to \mathbb{N} \cup \{\text{неопределено}\} \), где \( \mathbb{N} \) — множество натуральных чисел (обычно включающее 0). В отличие от общерекурсивных функций, которые определены для всех возможных наборов аргументов, частично рекурсивная функция может быть не определена для некоторых входных данных (то есть процесс вычисления может не завершаться). Класс частично рекурсивных функций совпадает с классом функций, вычислимых на машине Тьюринга, и с классом функций, представимых в виде лямбда-исчисления.

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

В основе построения частично рекурсивных функций лежат три базисные (исходные) функции:

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

Операторы

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

• Оператор суперпозиции (подстановки): если \( g \) — функция от \( m \) аргументов, а \( h_1, \dots, h_m \) — функции от \( n \) аргументов, то функция \( f(x_1, \dots, x_n) = g(h_1(x_1, \dots, x_n), \dots, h_m(x_1, \dots, x_n)) \) также является частично рекурсивной.
• Оператор примитивной рекурсии: задаёт функцию \( f \) от \( n+1 \) аргумента через базовый случай и рекурсивный шаг:

\[ f(0, x_1, \dots, x_n) = g(x_1, \dots, x_n) \] \[ f(y+1, x_1, \dots, x_n) = h(y, f(y, x_1, \dots, x_n), x_1, \dots, x_n) \] где \( g \) и \( h \) — уже построенные частично рекурсивные функции.

• Оператор минимизации (μ-оператор): для функции \( g(y, x_1, \dots, x_n) \) определяется функция

\[ f(x_1, \dots, x_n) = \mu y [g(y, x_1, \dots, x_n) = 0] \] которая ищет наименьшее натуральное \( y \), такое, что \( g(y, x_1, \dots, x_n) = 0 \), и при этом для всех \( z < y \) значение \( g(z, x_1, \dots, x_n) \) определено и не равно 0. Если такого \( y \) не существует, то \( f(x_1, \dots, x_n) \) не определена. Именно оператор минимизации вносит в класс функций частичность.

Классификация

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

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

Общерекурсивные функции

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

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

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

Свойства

• Замкнутость: класс частично рекурсивных функций замкнут относительно суперпозиции, примитивной рекурсии и минимизации.
• Универсальность: существует частично рекурсивная функция \( U(n, x) \), которая является универсальной для всех частично рекурсивных функций одной переменной. Это означает, что для любой частично рекурсивной функции \( f(x) \) найдётся такое число \( n \), что \( f(x) = U(n, x) \) для всех \( x \), где \( f \) определена.
• Нумерация: существует эффективная нумерация всех частично рекурсивных функций (например, по гёделевым номерам машин Тьюринга или по программам для рекурсивных функций).
• Нерекурсивность: проблема остановки (определение, завершится ли вычисление данной частично рекурсивной функции для данного аргумента) алгоритмически неразрешима. Это вытекает из теоремы Райса и неразрешимости проблемы остановки машины Тьюринга.

Применение

Теория алгоритмов

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

Математическая логика

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

Информатика

В программировании понятие частично рекурсивной функции соответствует функциям, вычисление которых может не завершиться (например, бесконечный цикл или рекурсия без базового случая). Многие языки программирования (например, Scheme, Haskell) основаны на лямбда-исчислении, которое эквивалентно по выразительной силе частично рекурсивным функциям.

Примеры

1. Функция сложения: \( add(x, y) = x + y \) — примитивно рекурсивна.
2. Функция Аккермана: \( A(m, n) \) — частично рекурсивна, но не примитивно рекурсивна. Определяется рекурсией с двумя аргументами:

• \( A(0, n) = n + 1 \)
• \( A(m+1, 0) = A(m, 1) \)
• \( A(m+1, n+1) = A(m, A(m+1, n)) \)

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

1. Функция, вычисляющая \( \mu y [y = x] \): для любого \( x \) возвращает \( x \) (определена для всех \( x \)), но если бы мы искали \( y \) такой, что \( y = x \) и \( x \) не существует, то функция была бы не определена.
2. Функция, решающая проблему остановки: не существует частично рекурсивной функции, которая для любой другой частично рекурсивной функции и её аргумента определяла бы, завершится ли вычисление. Это доказывается диагонализацией.

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

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

Источники

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