7.7. Теорема Мучника-Фридберга: выигрышные условия

Итак, пусть фиксирована программа р, которой Р хочет помешать разрешать множество X относительно множества У. Что он должен для этого делать? (Мы будем описывать всё происходящее с его точки зрения.)

В начале Р получает некоторое указание и некото­рый элемент, с ним согласованный. Все дальнейшие ука­зания должны быть сильнее этого — мы всегда должны указывать включить определённые числа в X и У и не включать некоторые другие (и тех, и других — конеч­ное множество). Кроме того, есть некоторый начальный элемент — начальная пара множеств. Со временем И уве­личивает эти множества по собственному усмотрению;единственное, как мы можем на это повлиять — давая указания.

Итак, что же мы делаем? На первом шаге выберем какое-то число х, не входящее в начальное значение X и не затронутое начальным указанием. В нашем первом указании мы попросим не включать это х в X, то есть добавим х во вторую компоненту начального указания, которую мы когда-то обозначали А~. (Если бы мы хоте­ли, чтобы программа не разрешала У, мы бы действовали симметрично и добавляли бы число в четвёртую компо­ненту, которая обозначалась В~.)

Что это нам даёт? Если мы будем и дальше дублиро­вать первое указание, то мы добьёмся, чтобы число х не принадлежало предельному множеству X. Но если в ка­кой-то момент мы передумаем и захотим, чтобы х при­надлежало X, это можно — достаточно изъять х из А~ и добавить его в А+, что не вызовет пата. (Заметим, что это новое указание не будет сильнее прежнего — но по-прежнему будет сильнее начального, а только это и требуется.)

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

Покажем, что эта стратегия действительно выигрыш­ная. Есть два случая. Если мы в какой-то момент пробу­дились, то по построению программа р даёт неправиль­ный ответ на числе х. Если же мы так и не пробудились, то программа р не даёт на х никакого ответа (при пре­дельном значении оракула). Почему? В самом деле, лю­бой такой ответ зависит от конечного числа вопросов к оракулу и требует конечного числа шагов работы — так что на достаточно далёком шаге игры, когда все нужные числа в оракуле появятся и времени на вычисление будет достаточно, мы должны были бы пробудиться.

Вычислимость нашей стратегии (в том числе вычи­слимая зависимость от параметра, то есть от програм­мы р) очевидна. Осталось объяснить лишь, почему число различных указаний будет конечно. На самом деле их мо­жет быть максимум два — если мы когда-то пробужда­лись, чтобы далее заснуть навеки (а если не пробужда­лись, то вообще одно).