Рекурсивно перечислимые множества

Рекурсивно перечислимое множество (также называемое частично разрешимым, полуразрешимым или перечислимым по Тьюрингу) — это множество натуральных чисел, для которого существует алгоритм (машина Тьюринга), который перечисляет все его элементы, возможно, с повторениями, но не обязательно в порядке возрастания. Формально, множество \( A \subseteq \mathbb{N} \) является рекурсивно перечислимым, если существует алгоритм, который на входе \( n \in \mathbb{N} \) останавливается и выдаёт ответ «да» тогда и только тогда, когда \( n \in A \); если \( n \notin A \), алгоритм может либо работать бесконечно, либо остановиться с ответом «нет», но не обязан этого делать. Это одно из центральных понятий теории алгоритмов и теории вычислимости, введённое в 1930-х годах в работах Алонзо Чёрча, Стивена Клини и Алана Тьюринга.

Определение и формализация

Рекурсивно перечислимые множества определяются через понятие частичной рекурсивной функции. Множество \( A \) называется рекурсивно перечислимым, если его характеристическая функция \( \chi_A \) является частично рекурсивной, то есть существует алгоритм, который для любого \( n \in \mathbb{N} \) останавливается и возвращает 1, если \( n \in A \), и не останавливается (или останавливается с другим значением) в противном случае. Эквивалентное определение: \( A \) рекурсивно перечислимо, если существует вычислимая функция \( f: \mathbb{N} \to \mathbb{N} \), такая что \( A = \{ f(0), f(1), f(2), \dots \} \), то есть множество является областью значений некоторой всюду определённой вычислимой функции.

Связь с разрешимостью

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

История

Понятие рекурсивно перечислимых множеств возникло в рамках формализации понятия алгоритма в 1930-х годах. Алонзо Чёрч в 1936 году сформулировал тезис Чёрча, согласно которому интуитивное понятие вычислимости совпадает с рекурсивными функциями. Стивен Клини ввёл термины «рекурсивно перечислимое» и «частично рекурсивное» в 1943 году. Алан Тьюринг в 1936 году описал машину Тьюринга и доказал неразрешимость проблемы остановки, что стало фундаментом для теории рекурсивно перечислимых множеств. В 1940-х годах Эмиль Пост и другие исследователи развили теорию степеней неразрешимости, классифицируя рекурсивно перечислимые множества по их сложности.

Классификация и свойства

Основные свойства

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

Иерархия арифметической иерархии

Рекурсивно перечислимые множества образуют первый уровень арифметической иерархии (обозначаемый \( \Sigma_1^0 \)). Множества, являющиеся дополнениями к рекурсивно перечислимым, образуют класс \( \Pi_1^0 \). Разрешимые множества соответствуют классу \( \Delta_1^0 = \Sigma_1^0 \cap \Pi_1^0 \). Более высокие уровни иерархии включают множества, определяемые более сложными формулами с кванторами.

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

Рекурсивно перечислимые множества классифицируются по тьюринговой степени — классу эквивалентности по отношению тьюринговой сводимости. Наименьшая степень — рекурсивная (разрешимые множества). Существует наибольшая степень среди рекурсивно перечислимых — степень проблемы остановки, обозначаемая \( \mathbf{0'} \). Между ними существует бесконечная иерархия степеней, изученная в работах Поста, Клини и других.

Примеры

• Проблема остановки: Множество \( K = \{ e \mid \text{машина Тьюринга с индексом } e \text{ останавливается на входе } e \} \) является рекурсивно перечислимым, но не разрешимым.
• Множество всех доказуемых формул в формальной арифметике: По теореме Гёделя о неполноте, множество истинных арифметических утверждений не является рекурсивно перечислимым, но множество доказуемых утверждений (в достаточно сильной формальной системе) рекурсивно перечислимо.
• Множество всех простых чисел: Является разрешимым, а следовательно, и рекурсивно перечислимым.
• Множество всех пар (e, x), таких что машина Тьюринга с индексом \( e \) останавливается на входе \( x \): Классический пример рекурсивно перечислимого, но не разрешимого множества.

Применение

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

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

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

В теории моделей и теории доказательств рекурсивно перечислимые множества описывают множества аксиом и теорем формальных систем. Например, множество аксиом арифметики Пеано рекурсивно перечислимо, а множество всех истинных утверждений арифметики — нет.

В информатике

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

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

Понятие рекурсивно перечислимого множества опирается на тезис Чёрча — Тьюринга, который не является формально доказуемым, но широко принят в математике. Некоторые исследователи, такие как Грегори Чейтин, указывали на ограничения классической теории вычислимости, связанные с неоднозначностью понятия «алгоритм» в квантовых вычислениях. Однако в рамках классической математики рекурсивно перечислимые множества остаются фундаментальным инструментом.

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

• Существует рекурсивно перечислимое множество, которое не является разрешимым, но его дополнение также рекурсивно перечислимо? Нет, по теореме Поста это означало бы разрешимость.
• Проблема остановки является «наиболее сложным» рекурсивно перечислимым множеством в смысле тьюринговой сводимости.
• В 1944 году Эмиль Пост сформулировал проблему о существовании рекурсивно перечислимого множества, которое не является ни разрешимым, ни тьюрингово полным (проблема Поста). Она была решена в 1956 году Ричардом Фридбергом и Альбертом Мучником независимо друг от друга с помощью метода приоритета.

Источники

• Клини С. К. Введение в метаматематику. — М.: Иностранная литература, 1957.
• Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.: Мир, 1972.
• Тьюринг А. О вычислимых числах, с приложением к проблеме разрешимости // Математические основы информатики. — 1936.
• Пост Э. Рекурсивно перечислимые множества и их проблемы разрешимости // Bulletin of the American Mathematical Society. — 1944. — Т. 50. — С. 284–316.
• Чёрч А. Замечание о проблеме разрешимости // Journal of Symbolic Logic. — 1936. — Т. 1. — С. 40–41.