Рекурсивное множество

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

Определение

Пусть \(\mathbb{N}\) — множество натуральных чисел. Подмножество \(A \subseteq \mathbb{N}\) называется рекурсивным, если его характеристическая функция

\[ \chi_A(x) = \begin{cases} 1, & \text{если } x \in A, \\ 0, & \text{если } x \notin A \end{cases} \]

является рекурсивной (вычислимой) функцией. Иными словами, существует машина Тьюринга или другая эквивалентная модель вычислений, которая для любого входного числа \(x\) останавливается и выдает ответ «да» (1) или «нет» (0), правильно определяя принадлежность \(x\) множеству \(A\).

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

Свойства

Замкнутость относительно теоретико-множественных операций

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

• Объединение: если \(A\) и \(B\) рекурсивны, то \(A \cup B\) рекурсивно.
• Пересечение: если \(A\) и \(B\) рекурсивны, то \(A \cap B\) рекурсивно.
• Дополнение: если \(A\) рекурсивно, то его дополнение \(\mathbb{N} \setminus A\) также рекурсивно (в отличие от рекурсивно перечислимых множеств, для которых дополнение может быть нерекурсивно).

Связь с рекурсивно перечислимыми множествами

• Всякое рекурсивное множество является рекурсивно перечислимым (РП). Обратное неверно: существуют РП-множества, не являющиеся рекурсивными (например, множество номеров программ, останавливающихся на пустом входе — проблема остановки).
• Множество \(A\) рекурсивно тогда и только тогда, когда и \(A\), и его дополнение \(\mathbb{N} \setminus A\) являются рекурсивно перечислимыми. Это альтернативное характеристическое свойство.

Разрешимость

Рекурсивные множества — это в точности те множества, для которых задача принадлежности (membership problem) алгоритмически разрешима. Например:

• Множество чётных чисел рекурсивно (проверка деления на 2).
• Множество простых чисел рекурсивно (существует алгоритм проверки простоты).
• Множество чисел, являющихся номерами машин Тьюринга, останавливающихся на пустом входе, не рекурсивно (неразрешимо).

Примеры

1. Конечные и коконечные множества. Любое конечное множество натуральных чисел рекурсивно (можно проверить перебором). Любое коконечное множество (дополнение конечно) также рекурсивно, так как его дополнение конечно и рекурсивно.
2. Арифметические прогрессии. Множество чисел, кратных заданному числу \(d\), рекурсивно.
3. Множество простых чисел. Рекурсивно, так как существует алгоритм проверки простоты (например, деление на все числа до \(\sqrt{n}\)).
4. Множество квадратов натуральных чисел. Рекурсивно (проверка, является ли число полным квадратом).
5. Множество степеней двойки. Рекурсивно.

Классификация в иерархиях

Арифметическая иерархия

В арифметической иерархии рекурсивные множества занимают самый низкий уровень: они соответствуют классу \(\Sigma_0^0\) и \(\Pi_0^0\), а также \(\Delta_0^0\). Говоря неформально, свойство принадлежности к рекурсивному множеству выражается формулой без кванторов (или с ограниченными кванторами).

Степени неразрешимости

Рекурсивные множества имеют наименьшую степень неразрешимости — степень \(0\) (нулевую). Все нерекурсивные множества имеют степень больше \(0\), например, степень проблемы остановки \(0'\).

Отличия от рекурсивно перечислимых множеств

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

В теории алгоритмов

Рекурсивные множества служат фундаментом для определения более сложных классов разрешимости. Понятие рекурсивности лежит в основе:

• Теоремы Райса о неразрешимости нетривиальных свойств программ.
• Построения неразрешимых проблем (проблема остановки, проблема эквивалентности программ).
• Классификации задач по степени сложности (m-сводимость, тьюринговы степени).

В математической логике

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

• Арифметика Пресбургера (теория сложения натуральных чисел) разрешима.
• Арифметика Пеано (с умножением) неразрешима.
• Теория вещественно замкнутых полей разрешима (теорема Тарского).

В компьютерных науках

В компьютерных науках рекурсивные множества соответствуют задачам, для которых существует алгоритм, всегда дающий точный ответ. Это:

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

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

• Понятие рекурсивного множества было введено в 1930-х годах Алонзо Чёрчем, Аланом Тьюрингом и другими основателями теории вычислимости как часть формализации «эффективно вычислимого».
• Известно, что существуют рекурсивные множества, которые не являются «простыми» в интуитивном смысле — например, множество чисел, которые не являются номерами машин Тьюринга, останавливающихся на пустом входе, рекурсивно (поскольку это дополнение рекурсивно перечислимого множества).
• В теории рекурсии доказано, что существует рекурсивное множество, порождающее при перечислении сколь угодно сложные паттерны, но при этом алгоритм проверки остаётся простым.

Источники

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