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

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

Определение и основные характеристики

Для формального определения обычно используется понятие машины Тьюринга. Множество натуральных чисел \( A \subseteq \mathbb{N} \) называется рекурсивно перечислимым (или частично разрешимым), если существует машина Тьюринга, которая, получив на вход произвольное число \( n \in \mathbb{N} \), останавливается и выдаёт ответ «да» тогда и только тогда, когда \( n \in A \). Если \( n \notin A \), машина либо останавливается с ответом «нет», либо вообще не останавливается (зацикливается). Альтернативное определение: множество \( A \) рекурсивно перечислимо, если существует машина Тьюринга, которая последовательно печатает все элементы \( A \) (возможно, с повторениями) без выдачи посторонних чисел.

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

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

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

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

1. Множество чётных чисел: очевидно разрешимо и, следовательно, рекурсивно перечислимо.
2. Множество простых чисел: разрешимо (алгоритм проверки простоты существует), рекурсивно перечислимо.
3. Множество значений частично рекурсивной функции: по определению, любая частично рекурсивная функция задаёт рекурсивно перечислимое множество своих значений.
4. Проблема остановки: множество пар (программа, входные данные), для которых программа останавливается. Это классический пример рекурсивно перечислимого, но не разрешимого множества. Алгоритм может перечислить все такие пары, но не может для произвольной пары определить, остановится ли программа.
5. Множество теорем формальной арифметики: согласно теореме Гёделя о неполноте, это множество рекурсивно перечислимо, но не разрешимо.

Свойства и теоремы

Теорема Поста

Теорема Эмиля Поста (1944) устанавливает связь между рекурсивно перечислимыми множествами и разрешимыми множествами. Она гласит: множество \( A \) является разрешимым тогда и только тогда, когда и само \( A \), и его дополнение \( \mathbb{N} \setminus A \) являются рекурсивно перечислимыми. Это означает, что неразрешимость рекурсивно перечислимого множества возникает именно из-за того, что его дополнение не является рекурсивно перечислимым.

Критерий перечислимости (теорема о проекции)

Существует эквивалентное определение: множество \( A \) рекурсивно перечислимо тогда и только тогда, когда существует разрешимое отношение \( R(x, y) \) (т.е. разрешимое множество пар) такое, что: \[ A = \{ x \mid \exists y \, R(x, y) \}. \] Иными словами, \( A \) — это проекция разрешимого множества на первую координату. Это подчёркивает, что рекурсивно перечислимые множества — это множества, которые можно получить, «спроецировав» разрешимое множество.

Проблема остановки

Проблема остановки — это множество \( K = \{ \text{программа } P, \text{входные данные } x \mid P(x) \text{ останавливается} \} \). Алан Тьюринг (1936) доказал, что проблема остановки является рекурсивно перечислимым, но не разрешимым множеством. Это, пожалуй, самый известный пример неразрешимости. Доказательство использует диагональный метод и приводит к парадоксу, аналогичному парадоксу лжеца.

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

В теории сложности вычислений рекурсивно перечислимые множества относятся к классу RE (Recursively Enumerable). Существует также класс co-RE, который состоит из дополнений рекурсивно перечислимых множеств (т.е. множеств, для которых существует алгоритм, проверяющий непринадлежность). Теорема Поста показывает, что R (разрешимые множества) — это пересечение RE и co-RE.

Интуитивная интерпретация и важность

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

См. также

• Теория алгоритмов
• Машина Тьюринга
• Разрешимое множество
• Проблема остановки
• Частично рекурсивная функция
• Теорема Поста

Источники

1. Клини С. К. «Введение в метаматематику» (1952). — Классический учебник, содержащий основные определения и теоремы.
2. Роджерс Х. «Теория рекурсивных функций и эффективная вычислимость» (1967). — Подробное изложение теории вычислимости.
3. Тьюринг А. «О вычислимых числах с приложением к Entscheidungsproblem» (1936). — Основополагающая статья, вводится понятие машины Тьюринга и доказывается неразрешимость проблемы остановки.
4. Пост Э. «Рекурсивно перечислимые множества положительных целых чисел и их проблемы разрешения» (1944). — Статья, вводящая теорему Поста и понятие m-сводимости.
5. Мальцев А. И. «Алгоритмы и рекурсивные функции» (1965). — Классическое учебное пособие на русском языке.