7.8. Теорема Мучника-Фридберга: метод приоритета

Теперь можно забыть о конкретной природе элемен­тов и указаний и показать, что если есть последователь­ность выигрышных условий а\, а2, ■ ■ ■, причём выигрыш­ные стратегии для Р вычислимо зависят от г, то есть па­ра перечислимых множеств, удовлетворяющая всем усло­виям.

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

Что же происходит, если какой-то из руководителей неожиданно изменил своё указание? В этом случае мы следуем его указанию, не обращая внимания на указания менее приоритетных, а перед ними извиняемся и гово­рим, что пригласили их слишком рано. Но затем мы снова постепенно приглашаем их по той же схеме.

Покажем, что каждый руководитель рано или позд­но получит возможность бессменно руководить. В самом деле, первый вообще ничего не знает о других, поскольку его указания самые важные и всегда исполняются. Зна­чит, в некоторый момент он перестанет давать новые указания. Запущенная после этого инкарнация второго руководителя уже не встретит никаких помех, посколь­ку лишь изменение указаний первого может ей помешать, поэтому и указания второго стабилизируются, и т. д. При этом каждый руководитель добьётся выполнения своего свойства.

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

Вычислимость всех стратегий всех руководителей (плюс вычислимая зависимость от номера руководите­ля) гарантирует вычислимость описанного процесса, так что получатся перечислимые множества, которые удо­влетворяют всем условиям.

Это рассуждение завершает доказательство теоремы Мучника-Фридберга. >

61. Покажите, что существует счётное число перечисли­мых множеств, никакие два их которых не сравнимы по Тью­рингу.