7.5. Несравнимые множества

Определение сводимости по Тьюрингу (напомним, что А сводится по Тьюрингу к В, если множество А раз­решимо с оракулом для В) можно рассматривать как способ сравнивать задачи разрешения различных мно­жеств «по трудности». (Если А <Ст В, то задача разреше­ния множества А в некотором смысле проще, чем задача разрешения множества В.)

Возникает множество естественных вопросов, свя­занных с такой классификацией. Например, существует ли самая трудная в мире задача разрешения, то есть та­кое множество А, что В <Ст А для любого множества В?

Ответ, как легко понять, отрицательный: в релятивизо-ванном относительно А мире есть свои неразрешимые множества (и даже А-перечислимые А-неразрешимые множества) — поскольку там выполнены обычные тео­ремы теории алгоритмов. (Можно также заметить, что поскольку различных программ счётное число, то при любом множестве А семейство всех А-разрешимых мно­жеств счётно.)

Другой, менее тривиальный вопрос такой: любые ли два множества сравнимы? Оказывается, что нет, как по­казывает следующая теорема, доказанная Клини и По­стом.

Теорема 49. Существуют два множества А ж В, для которых А В ж В А. Эти множества можно взять О'-разрешимыми.

<] Множества А ж В должны удовлетворять таким требованиям: никакая программа, к которой присоеди­нён В-оракул, не разрешает множества А, и никакая про­грамма, к которой присоединён А-оракул, не разрешает множества В.

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

Опишем рассуждение более подробно. Назовём фраг­ментом функцию, которая определена на некотором (ко­нечном) начальном отрезке натурального ряда и прини­мает значения 0 и 1. Будем говорить, что множество А согласовано с фрагментом а, если характеристическая функция множества А продолжает а. Другими словами, согласованность с данным фрагментом означает опреде­лённое поведение множества на начальном отрезке нату­рального ряда.

Если фрагмент а2 продолжает фрагмент щ (то есть определён на большем отрезке с сохранением прежних значений на меньшем), то, очевидно, согласованность с ним накладывает больше ограничений на множество.

Лемма. Пусть а и Ь — два фрагмента, ар — програм­ма, содержащая вызовы внешней процедуры. Тогда су­ществуют продолжения а1 и Ь1 этих фрагментов с таким свойством: ни для каких множеств А и В, согласованных с а1 и Ь1, программа р, имея доступ к характеристической функции для В, не будет разрешать множество А.

Доказав эту лемму, можно поочерёдно рассматривать все программы и гарантировать, что ни одна из них не разрешает А относительно В. Если при этом чередо­вать А ж В в применении этой леммы, то одновременно можно гарантировать, что ни одна программа не разре­шает В относительно А.

(Замечание. Очевидно, можно предполагать, что а' ж Ь1 длиннее а ж Ь — их всегда можно искусственно удли­нить. Тогда в пределе мы получим бесконечные последо­вательности, являющиеся характеристическими функци­ями двух искомых множеств. Впрочем, это не обязатель­но: если в пределе вдруг получатся конечные фрагмен­ты — возьмём любые множества, с ними согласованные.)

Итак, для построения множеств А ж В осталось дока­зать лемму. (К вопросу о О'-вычислимости мы ещё вер­нёмся.)

В формулировку леммы множества А ж В входят несимметрично, поэтому и рассуждение будет несим­метричное. Фиксируем некоторое число х, которое не входит в область определения фрагмента а, и зададим себе вопрос: существует ли такое множество В, согла­сованное с фрагментом Ь, что после присоединения его характеристической функции к программе р эта про­грамма даёт на входе х какой-то из ответов «да» и «нет». Если такого множества нет, то вообще заботиться не о чем — утверждение леммы будет верным, если просто положить а' = а, Ь1 = Ь.

Пусть такое множество В существует. Проследим за работой программы р на входе х для этого множества В. Прежде чем выдать свой ответ, программа может неко­торое конечное число раз вызывать характеристическую функцию множества В. Возьмём фрагмент Ь1, с которым В согласовано, и притом достаточно длинный, чтобы по­крыть и зафиксировать все те места, к которым обраща­лась программа р. Тогда программа р будет давать тот же самый ответ не только для множества В, но и для любых множеств, согласованных с У. Остаётся обеспе­чить, чтобы этот ответ был неверным, что можно сде­лать, включив х в область определения а1 и выбрав а1 (х) противоречащим этому ответу. Лемма доказана.

Осталось лишь доказать утверждение теоремы, отно­сящееся к О'-вычислимости, для чего надо убедиться, что построение а1 и Ь1 в доказательстве леммы можно сде­лать О'-алгоритмическим. Ключевой момент здесь — от­вет на сформулированный при доказательстве леммы во­прос. Конечно, буквально перебрать континуум возмож­ных множеств В, согласованных с фрагментом Ь, невоз­можно. Но это и не требуется — надо просто просматри­вать все варианты работы программы р. Когда она за­даёт вопрос про не входящее в Ь число, просмотр развет­вляется на два направления в зависимости от двух воз­можностей. Получается ветвящееся дерево вариантов, и вопрос состоит в том, получается ли ответ «да» или «нет» хоть на какой-то ветви. А этот вопрос можно перефор­мулировать как вопрос о том, остановится ли некоторая программа (а именно, программа, просматривающая па­раллельно все ветви и останавливающаяся, как только на одной из них появится ответ «да» или «нет»).

Это замечание и завершает доказательство теоре­мы. >

Гораздо более сложен вопрос о том, существуют ли не просто О'-разрешимые несравнимые по Тьюрингу множе­ства, а перечислимые несравнимые по Тьюрингу множе­ства. Эту проблему (так называемую проблему Поста) независимо решили американский математик Фридберг и Альберт Абрамович Мучник; интересно, что для по­строения перечислимых несравнимых множеств они использовали один и тот же подход, который получил на­звание «метод приоритета».