7.6. Теорема Мучника-Фридберга: общая схема конструкции

Теорема 50. Существуют несравнимые по Тьюрингу перечислимые множества.

Мы приводим доказательство этой теоремы как при­мер более изощрённой техники, используемой в теории вычислимых функций. Однако надо иметь в виду, что в 1960-ые и 1970-ые годы передний край этой области ушёл далеко за горизонт, и приводимое ниже рассуждение ста­ло скорее образцом простоты, чем сложности.

<] Итак, мы хотим построить два перечислимых мно­жества, ни одно из которых не сводится к другому по Тьюрингу. Мы будем строить их по шагам; на каждом шаге будет известна лишь конечная часть будущих мно­жеств. Нам будет удобна такая терминология.

Будем называть элементом произвольную пару ко­нечных множеств (А, В) натуральных чисел. Будем го­ворить, что элемент (А', В'} продолжает элемент (А, В), если А С А' и В С В'. Мы построим вычислимую после­довательность элементов, каждый из которых продолжа­ет предыдущий; в пределе (объединении) они дадут ис­комые перечислимые несравнимые множества.

Будем называть указанием четвёрку конечных мно­жеств (А+, А~, В+, В~), в которой А+ не пересекается с А~ и В+ не пересекается с В~. Слово «указание» объ­ясняется тем, что такие четвёрки указывают, чего мы хотим от элементов: А+ — это числа, которые должны входить в А, а А~ — числа, которые не должны входить в А; аналогично для В. Формально, мы говорим, что эле­мент (А, В) согласован с указанием (А+, А~, В+, В~), ес­ли А+ С А, А~ П А = 0, В+ С В, В~ П В = 0. Будем говорить, что указание и2 сильнее указания щ , если вся­кий элемент, согласованный с и2, согласован тещ (то есть каждая из четырёх частей указания может толькоувеличиться).

Пусть а(Х,У) — произвольное свойство пары мно­жеств Х,У С N. С каждым таким свойством свяжем некоторую игру двух персонажей — Руководителя (Р) и Исполнителя (И). Игра происходит так: вначале И предъявляет Р некоторое указание щ и некоторый эле­мент ео, согласованный с щ. Мы будем называть их начальным указанием и начальным элементом. (Как мы увидим, в окончательной конструкции руководителей бу­дет несколько, и начальное указание и элемент достаются свеженазначенному руководителю от его предшествен­ников — но об этом дальше). Р отвечает некоторым указанием щ, после этого И выбирает согласованный с ним элемент е\, затем Р выбирает и2, И выбирает е2 и так далее (игра продолжается бесконечно).

Правила игры таковы:

• Каждый следующий выбираемый И элемент должен продолжать предыдущий (и потому все они продол­жают начальный); он также должен быть согласо­ван с последним указанием Р, но может не быть согласован с его предыдущими указаниями.

• Все указания Р должны быть сильнее начального указания (но не обязаны быть сильнее его преды­дущих указаний!).

• Если очередное указание Р вызывает пат (то есть у И нет элемента, который был с ним согласован и продолжал предыдущий элемент), то игра заканчи­вается и Р проигрывает.

• Если игра бесконечна, то мы считаем Р победите­лем при выполнении двух условий. Первое из них состоит в том, что указания Р, начиная с некото­рого момента игры, не меняются.

• Наконец, второе условие состоит в том, что пре­дельные множества X и У удовлетворяют усло­вию а(Х,У), о котором мы говорили до началаописания игры. (Если г-ый элемент е,- есть (Х,-,У,-), то X и У есть объединения возрастающих цепочек множеств .V,) С Х\ С ■ ■ ■ и Уо С У\ С ■ ■ ■)

Будем называть условие выигрышным, если существу­ет вычислимая (реализуемая алгоритмом) стратегия для Р, гарантирующая его выигрыш. Дальнейший план дей­ствий такой. Мы покажем, что для любой программы р с вызовами внешней процедуры условие «р с оракулом для У не разрешает X» является выигрышным. (Это рас­суждение в значительной мере повторяет рассуждение из теоремы Клини- Поста, но несколько более сложно.) Бо­лее того, мы установим, что соответствующая стратегия вычислимо зависит от р.

С другой стороны, мы покажем, что для любого числа выигрышных условий а,-, для которых стратегии можно выбрать вычислимо зависящими от г, можно найти пару перечислимых множеств, удовлетворяющую всем услови­ям. Именно это последнее рассуждение будет использо­вать идею «приоритета»: у нас будет один исполнитель и счётное число руководителей, которым присвоены раз­ные уровни приоритета (главный, менее главный, ещё ме­нее главный и т.д.).