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

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

История возникновения

Понятие степени неразрешимости было введено американским математиком Стивеном Клини в 1943 году, а затем развито Эмилем Постом в 1944 году в его знаменитой работе «Recursively enumerable sets of positive integers and their decision problems». Пост поставил проблему, известную как проблема Поста: существуют ли неразрешимые рекурсивно перечислимые множества, которые не являются тьюрингово полными? Эта проблема стимулировала развитие теории степеней на протяжении нескольких десятилетий.

В 1950-х годах Джон Майхилл и Хартли Роджерс заложили основы современной теории степеней неразрешимости, введя понятие верхней полурешётки и изучив её свойства. В 1960-х годах Ричард Фридберг и Альберт Мучник независимо друг от друга разработали метод приоритета, который позволил доказать существование промежуточных степеней (между 0 и 0′), что частично решило проблему Поста. Впоследствии теория степеней стала одной из центральных областей теории вычислимости.

Основные определения

Тьюрингова сводимость

Говорят, что множество \(A\) тьюрингово сводимо к множеству \(B\) (обозначается \(A \leq_T B\)), если существует алгоритм (машина Тьюринга с оракулом), который, имея доступ к «оракулу» для \(B\), может решить проблему принадлежности для \(A\). Иными словами, \(A\) вычислимо относительно \(B\).

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

Степень неразрешимости (или тьюрингова степень) — это класс эквивалентности множеств натуральных чисел по отношению взаимной тьюринговой сводимости. Два множества \(A\) и \(B\) имеют одну и ту же степень, если \(A \leq_T B\) и \(B \leq_T A\). Обозначается степень множества \(A\) как \(\mathbf{a} = \deg(A)\).

Верхняя полурешётка

Множество всех степеней неразрешимости образует верхнюю полурешётку с операцией \(\cup\) (точная верхняя грань). Для любых двух степеней \(\mathbf{a}\) и \(\mathbf{b}\) существует степень \(\mathbf{a} \cup \mathbf{b}\), которая является наименьшей степенью, большей или равной обеим. Однако не для любой пары степеней существует точная нижняя грань.

Иерархия степеней

Наименьшая степень

Существует наименьшая степень неразрешимости, обозначаемая \(\mathbf{0}\). Она состоит из всех разрешимых (рекурсивных) множеств. Множество \(A\) имеет степень \(\mathbf{0}\) тогда и только тогда, когда оно разрешимо (существует алгоритм, определяющий принадлежность любого числа к \(A\)).

Степень проблемы остановки

Степень проблемы остановки (или степени \(0'\)) — это степень множества \(\emptyset'\), которое является тьюринговым скачком пустого множества. Проблема остановки (halting problem) для машин Тьюринга является классическим примером неразрешимой проблемы. Степень \(0'\) — это наибольшая степень среди рекурсивно перечислимых множеств (в смысле тьюринговой сводимости). Множества, имеющие степень \(0'\), называются тьюрингово полными.

Промежуточные степени

Одним из важнейших результатов теории степеней является существование промежуточных степеней — степеней, которые строго больше \(\mathbf{0}\), но строго меньше \(0'\). Этот результат был получен Фридбергом и Мучником (теорема Фридберга — Мучника). Существование таких степеней означает, что не все неразрешимые проблемы одинаково сложны: есть проблемы, которые сложнее разрешимых, но проще проблемы остановки.

Тьюрингов скачок

Для любой степени \(\mathbf{a}\) определена степень \(\mathbf{a}'\), называемая тьюринговым скачком \(\mathbf{a}\). Скачок — это операция, которая увеличивает степень: \(\mathbf{a} < \mathbf{a}'\). Повторное применение скачка порождает бесконечную возрастающую последовательность степеней: \[ \mathbf{0} < \mathbf{0}' < \mathbf{0}'' < \mathbf{0}''' < \cdots \] Эта последовательность называется итерацией тьюрингова скачка.

Свойства верхней полурешётки

Плотность

Верхняя полурешётка степеней неразрешимости обладает свойством плотности: для любых двух степеней \(\mathbf{a} < \mathbf{b}\) существует степень \(\mathbf{c}\) такая, что \(\mathbf{a} < \mathbf{c} < \mathbf{b}\). Это свойство было доказано Джеймсом Шёнфилдом в 1960-х годах.

Отсутствие максимальной степени

Не существует наибольшей степени неразрешимости: для любой степени \(\mathbf{a}\) существует степень \(\mathbf{b}\) такая, что \(\mathbf{a} < \mathbf{b}\). Это следует из того, что тьюрингов скачок всегда строго увеличивает степень.

Минимальные степени

Степень \(\mathbf{a}\) называется минимальной, если \(\mathbf{a} > \mathbf{0}\) и не существует степени \(\mathbf{c}\) такой, что \(\mathbf{0} < \mathbf{c} < \mathbf{a}\). Существование минимальных степеней было доказано Клиффордом Сполдингом в 1960-х годах. Минимальные степени представляют собой «атомы» в структуре степеней.

Классификация степеней

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

Степень \(\mathbf{a}\) называется рекурсивно перечислимой (р.п.), если в ней содержится хотя бы одно рекурсивно перечислимое множество. Класс р.п. степеней включает \(\mathbf{0}\) (разрешимые множества) и \(0'\) (проблема остановки), а также все промежуточные степени, существование которых доказано.

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

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

• \(\Sigma_1^0\)-множества — это в точности рекурсивно перечислимые множества.
• \(\Sigma_2^0\)-множества имеют степень, не превышающую \(0''\).
• И так далее.

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

За пределами арифметической иерархии находится гиперарифметическая иерархия, которая использует трансфинитные итерации тьюрингова скачка. Степени гиперарифметических множеств образуют более сложную структуру, но также поддаются классификации.

Применение в теории вычислимости

Проблема Поста

Проблема Поста, сформулированная в 1944 году, спрашивает: существует ли рекурсивно перечислимое множество, которое не является ни разрешимым, ни тьюрингово полным? Отрицательный ответ на этот вопрос означал бы, что все неразрешимые р.п. множества имеют степень \(0'\). Однако метод приоритета Фридберга — Мучника показал существование таких множеств, что дало положительный ответ на проблему Поста в её ослабленной формулировке.

Иерархия неразрешимости

Степени неразрешимости позволяют строить иерархии для конкретных математических проблем. Например, проблема разрешимости для теорий первого порядка (таких как арифметика Пресбургера, арифметика Пеано) может быть классифицирована по степеням неразрешимости. Арифметика Пресбургера разрешима, а арифметика Пеано неразрешима и имеет степень \(0'\).

Теория вычислимости на практике

В современной теории вычислимости степени неразрешимости используются для изучения относительной вычислимости, свойств оракулов, а также в теории случайности и алгоритмической информации. Например, понятие степени случайности (степени по Мартин-Лёфу) тесно связано с тьюринговыми степенями.

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

Несмотря на мощь теории степеней неразрешимости, она имеет ряд ограничений. Во-первых, структура верхней полурешётки чрезвычайно сложна и не поддаётся полному описанию в рамках обычной математики (например, она не является дистрибутивной). Во-вторых, многие важные вопросы остаются открытыми, например, проблема существования минимальных р.п. степеней (кроме \(\mathbf{0}\) и \(0'\)) была решена лишь частично. В-третьих, понятие тьюринговой сводимости не является единственным способом классификации неразрешимости; существуют и другие виды сводимости (например, m-сводимость, 1-сводимость), которые дают более тонкие иерархии.

Источники

1. Клини С. К. Введение в метаматематику. — М.: Издательство иностранной литературы, 1957.
2. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.: Мир, 1972.
3. Пост Э. Л. Рекурсивно перечислимые множества положительных целых чисел и их проблемы разрешимости // Успехи математических наук. — 1948. — Т. 3, № 1(23). — С. 3–29.
4. Фридберг Р. М. Две рекурсивно перечислимые множества, несравнимые по Тьюрингу // Математика. — 1959. — Т. 3, № 5. — С. 111–124.
5. Мучник А. А. Неразрешимость проблемы сводимости теории алгоритмов // Доклады АН СССР. — 1956. — Т. 108, № 2. — С. 194–197.
6. Шёнфилд Дж. Р. Степени неразрешимости. — М.: Наука, 1977.
7. Сполдинг К. Минимальные степени неразрешимости // Труды Американского математического общества. — 1966. — Т. 121. — С. 1–15.