Вычисления с оракулом

Релятивизация

Пусть фиксирована некоторая всюду определенная функция $$\alpha.$$ Тогда вся теория вычислимых функций может быть, как говорят, " релятивизована" относительно $$\alpha,$$ если во всех определениях и формулировках заменить вычислимые функции на функции, вычислимые относительно $$\alpha$$ (которые для краткости называют также $$\alpha$$ - вычислимыми ). При этом все сформулированные выше результаты остаются в силе, и доказательства остаются почти такими же.

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

Пусть E произвольноe множество пар вида $$\langle x, t\rangle$$, где x число, а t образец. Пусть $$\alpha$$ некоторая всюду определенная функция. Отберем в множестве E те пары, у которых вторые члены являются частью $$\alpha$$ ; первые члены таких пар образуют множество, которое мы обозначим $$E[\alpha ]$$.

Теорема 46. Множество X является $$\alpha$$ -перечислимым тогда и только тогда, когда $$X=E[\alpha ]$$ для некоторого перечислимого множества E. (Заметим, что в этом случае не требуется никакого специального условия типа корректности.)

Пусть X есть область определения вычислимой относительно $$\alpha$$ функции f. Тогда $$f=M[\alpha ]$$ для некоторого перечислимого корректного множества M. Оставим от всех троек в M только первый и третий члены; получится некоторое перечислимое множество E. Легко проверить, что $$E[\alpha ]$$ будет областью определения функции $$M[\alpha ]=f$$, так что $$E[\alpha ]=X$$.

Напротив, пусть $$X=E[\alpha ]$$ для некоторого $$\alpha.$$ Тогда рассмотрим множество M, которое получится, если в середину каждой пары из E добавить число 0. Ясно, что множество M будет корректным и что $$M[\alpha ]$$ будет функцией, определенной на $$X=E[\alpha ]$$ и принимающей только нулевые значения.

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

Теорема 47. Пусть $$\alpha$$ всюду определенная функция. Существует вычислимая относительно $$\alpha$$ функция двух аргументов, являющаяся универсальной для класса вычислимых относительно $$\alpha$$ функций одного аргумента.

Как и в других случаях, можно почти без изменений воспроизвести доказательство соответствующей нерелятивизованной теоремы. Фиксируем какой-то язык программирования (предусматривающий на этот раз вызовы внешних процедур) и перенумеруем все программы, которые включают в себя вызовы внешней процедуры $$\alpha.$$ Теперь в качестве универсальной можно взять функцию

Мы использовали нижний индекс, чтобы подчеркнуть, что функция $$U_{\alpha }$$ зависит от $$\alpha.$$ Впрочем, текст вычисляющей ее программы от $$\alpha$$ не зависит (хотя, естественно, содержит вызовы функции $$\alpha$$ ).

Поучительно привести и другое доказательство, которое опирается на определение вычислимости в терминах корректных перечислимых множеств.

Рассмотрим универсальное перечислимое множество Z четверок вида $$\langle n, x,y,t\rangle$$, где n, x и y числа, а t образец. Говоря об универсальности, мы имеем в виду, что при различных n среди сечений Zn содержатся все перечислимые множества троек.

Среди этих перечислимых множеств троек могут быть и корректные, и некорректные. Мы хотим принудительно корректировать некорректные сечения, не меняя корректных. Другими словами, мы хотим построить новое перечислимое множество Z' с такими свойствами: во-первых, все сечения Z' корректны; во-вторых, если сечение Zn при некотором n было корректно, то оно не изменилось ( Z'n=Zn ).

Это делается просто: нужно перечислять Z, отбрасывая (не пропуская в Z' ) элементы, добавление которых делает некоторое сечение некорректным. Итак, мы построили перечислимое множество Z', универсальное для класса корректных перечислимых множеств.

Теперь легко указать корректное множество W, задающее универсальную $$\alpha$$ -вычислимую функцию. Именно, тройка $$\langle \langle n,x\rangle, y, t\rangle$$ (теперь ее первым членом является пара, так как универсальная функция зависит от двух аргументов) принадлежит W, если $$\langle n,x,y,t\rangle\hm\in Z'$$. Легко понять, что множество W корректно. При данной функции $$\alpha$$ это корректное множество задает некоторую $$\alpha$$ -вычислимую функцию $$U_{\alpha }$$ двух аргументов; ее n -ое сечение есть $$Z'_{n}[\alpha ]$$, где Z'n n -ое сечение множества Z'. Поэтому среди сечений функции $$U_{\alpha }$$ встречаются все $$\alpha$$ -вычислимые функции, что и требовалось доказать.

В релятивизованной теории алгоритмов имеется, конечно, и аналог понятия главной универсальной функции: $$\alpha$$ -вычислимую функцию двух аргументов называют главной универсальной функцией для класса $$\alpha$$ -вычислимых функций одного аргумента, если она $$\alpha$$ -вычислима, универсальна для класса $$\alpha$$ -вычислимых функций одного аргумента и для всякой $$\alpha$$ -вычислимой функции V двух аргументов существует всюду определенная $$\alpha$$ -вычислимая функция s одного аргумента (" транслятор"), для которой V(n,x)=U(s(n),x) при всех n и x.

Обычное доказательство (теорема 15) показывает, что главные универсальные функции для класса $$\alpha$$ -вычислимых функций существуют. Более того, можно заметить, что построенная при доказательстве (см. выше) функция s будет не только $$\alpha$$ -вычислимой, но и просто вычислимой (в одном из вариантов доказательства функция s имела вид $$x\hm\mapsto[n,x]$$, где квадратные скобки обозначают фиксированную вычислимую нумерацию пар, а n некоторое фиксированное число).

Удобно, говоря о номерах $$\alpha$$ -вычислимых функций, иметь в виду их номера в таких " сильно главных" нумерациях. Естественная нумерация (порядковые номера программ) является " сильно главной" нумерацией.

Говоря о релятивизованной теории алгоритмов, иногда употребляют такую метафору. Пусть A какое-то неразрешимое множество. Может оказаться, что есть такая внеземная цивилизация, которой множество A кажется разрешимым; глядя на число x, они сразу понимают, лежит ли оно в множестве A или нет, и эта проверка такое же элементарное действие в их программах, как у нас сравнение двух чисел. Тогда вся их теория алгоритмов будет автоматически релятивизованной относительно A, но они этого замечать не будут и потому прочтут наши рассуждения вплоть до этого раздела (не включая его) и согласятся со всеми теоремами. Более того, они могут прочесть и этот раздел о релятивизации но то, что для них будет B -вычислимым, для нас будет A - B -вычислимым (вычислимым с двумя оракулами A и B ).

Впрочем, к этой метафоре не стоит относиться слишком серьезно.

0'-вычисления

В этом разделе мы рассмотрим вычислимость относительно m -полного перечислимого множества. Любые два таких множества m -сводятся друг к другу, и тем более T -сводятся друг к другу. Поэтому если какая-то функция вычислима относительно одного из них, то она вычислима и относительно другого. Такие функции называют 0' -вычислимыми.

Вспоминая, что множество пар $$\{\langle p,x\rangle\mid \text{программа~$p$}$ завершает работу на входе~$x\}$$ является одним из m -полных перечислимых множеств, можно сказать, что 0' -вычислимые функции вычисляются машинами, которым придан специальный оракул, решающий проблему остановки: этому оракулу посылают программу и вход, и он отвечает, останавливается ли эта программа на этом входе или не останавливается. (При этом посылаемая на экспертизу программа самая обычная, без обращений к оракулу.)

Ясно, что любое перечислимое множество является 0' -разрешимым, так как сводится к m -полному перечислимому множеству. (Обратное, очевидно, неверно дополнение к перечислимому неразрешимому множеству также 0' -разрешимо, но не перечислимо.)

Имеется следующее простое описание 0' -вычислимых функций:

Теорема 48. (а) Пусть T всюду определенная вычислимая функция двух натуральных аргументов. Перейдем к пределу по второму аргументу, рассмотрев функцию

$$t \colon x \mapsto \lim_{n\to\infty} T(x,n).$$

(Эта функция уже не обязана быть всюду определенной, так как при некоторых x указанный предел может не существовать.) Функция t будет 0' -вычислимой. (б) Всякая 0' -вычислимая функция t может быть получена указанным образом из некоторой вычислимой всюду определенной функции T.

(a) Пусть T вычислимая всюду определенная функция двух аргументов. Назовем пару $$\langle x,n\rangle$$ стабильной, если T(x,n)=T(x,m) для данного x и для всех m>n. Заметим, что множество нестабильных пар перечислимо (найдя две пары $$\langle x,n\rangle$$ и $$\langle x,n\rangle$$ с n<m и $$T(x,n) \ne T(x,m)$$, мы включаем пару $$\langle x,n\rangle$$ в перечисление всех нестабильных пар). Поэтому множество нестабильных пар 0' -разрешимо. Другими словами, 0' -алгоритм для любой пары может проверить, стабильна ли она.

Рассмотрим теперь следующий 0' -алгоритм вычисления предельной функции t. Получив вход x, мы рассматриваем по очереди пары $$\langle x,0\rangle, \langle x,1\rangle,..$$. и для каждой из них проверяем, является ли она стабильной. Как только стабильная пара $$\langle x,n\rangle$$ будет обнаружена, значение T(x,n) выдается в качестве результата. Очевидно, описанный 0' -алгоритм вычисляет функцию t.

(б) Докажем теперь обратное утверждение. Пусть t частичная 0' -вычислимая функция одного аргумента. Нам надо построить вычислимую (в обычном смысле) всюду определенную функцию двух аргументов T, для которой

$$t (x) = \lim_{n\to\infty} T(x,n)$$

при всех x (и обе части этого равенства определены одновременно). Прежде всего мы сделаем себе небольшое послабление, разрешив функции T принимать также и некоторое специальное значение, которое мы будем обозначать звездочкой. При этом$$\lim_{n\to\infty} T(x,n) = a$$ означает, что при всех достаточно больших n значение T(x,n) равно a (и, в частности, не равно $$\star$$ ).

Такое послабление на самом деле несущественно: если в последовательности, в которой есть звездочки, каждую из них заменить на два различных подряд идущих члена (все равно каких), то последовательность будет иметь прежний предел (или по-прежнему не иметь предела).

Теперь определим функцию T. По предположению функция t вычисляется некоторой программой p, имеющей доступ к характеристической функции некоторого перечислимого множества K. Обозначим через Kn конечное подмножество множества K, состоящее из тех его элементов, которые успели обнаружиться за n шагов перечисления множества K. Вычисляя T(x,n), мы сделаем n шагов работы программы p, при этом используя вместо K его конечное приближение Kn. Если за эти n шагов программа p не даст ответа (что может быть по разным причинам отведенное ей время может быть недостаточно, Kn может отличаться от K, да и вообще функция t на x может быть не определена), то $$T(x,n)=\star$$. Если же за n шагов программа ответ даст, то этот ответ и будет значением T(x,n) (за одним исключением, о котором мы скажем позже).

Попробуем доказать, что$$t(x)=\lim_{n\to\infty}T(x,n).$$ Пусть t(x) равно некоторому a. Тогда работа программы p (с правильным оракулом K ) через некоторое время завершается и дает ответ a. При этом вычислении используется лишь конечное число вопросов к оракулу. Поэтому при достаточно большом n множество Kn в этих местах уже будет совпадать с K. Увеличив n еще, если надо (чтобы оно превзошло время работы программы p ), мы можем гарантировать, что при этом n и при всех больших n значение T(x,n) будет равно a.

Но нам надо еще доказать, что если предел существует и равен a, то t(x)=a. Здесь нас ожидает трудность, состоящая в следующем. Пусть при настоящем K работа программы p не завершается. Но тем не менее может получиться так, что при каждом n наше вычисление завершится за счет того, что множество Kn отличается от настоящего K, и даже случайно все эти вычисления дадут одинаковый ответ.

Чтобы справиться с этой трудностью, изменим определение функции T. А именно, договоримся, что если при вычислении T(x,n) и T(x,n-1) протоколы обращений к оракулу были разными (задавались разные вопросы или были получены разные ответы на одинаковые вопросы), то $$T(x,n)=\star$$. Это не портит нашего предыдущего рассуждения, поскольку там при больших n задаваемые вопросы и даваемые ответы такие же, как в " настоящем" вычислении. Зато теперь мы можем быть уверены, что если последовательность T(x,0),T(x,1),... имеет предел, то и t(x) определено. В самом деле, если она имеет предел, то содержит конечное число звездочек. Значит, при всех достаточно больших n оракулу задаются одни и те же вопросы и получаются одни и те же ответы. Значит, эти ответы правильны, так как в пределе Kn стремится к K. Поэтому настоящее вычисление также завершается (с тем же ответом).

  61. Приведенное в задаче 14 определение вычислимого действительного числа можно релятивизовать относительного любого множества A. Покажите, что число $$\alpha$$ является 0' -вычислимым тогда и только тогда, когда оно является пределом вычислимой последовательности рациональных чисел.

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

Определение сводимости по Тьюрингу (напомним, что A сводится по Тьюрингу к B, если множество A разрешимо с оракулом для B ) можно рассматривать как способ сравнивать задачи разрешения различных множеств " по трудности". (Если A <=T B, то задача разрешения множества A в некотором смысле проще, чем задача разрешения множества B.)

Возникает множество естественных вопросов, связанных с такой классификацией. Например, существует ли самая трудная в мире задача разрешения, то есть такое множество A, что B <=T A для любого множества B? Ответ, как легко понять, отрицательный: в релятивизованном относительно A мире есть свои неразрешимые множества (и даже A -перечислимые A -неразрешимые множества) поскольку там выполнены обычные теоремы теории алгоритмов. (Можно также заметить, что поскольку различных программ счетное число, то при любом множестве A семейство всех A -разрешимых множеств счетно.)

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

Теорема 49. Существуют два множества A и B, для которых $$A{\not\leq_T} B$$ и $$B{\not\leq_T} A$$. Эти множества можно взять 0' -разрешимыми.

Множества A и B должны удовлетворять таким требованиям: никакая программа, к которой присоединен B -оракул, не разрешает множества A, и никакая программа, к которой присоединен A -оракул, не разрешает множества B.

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

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

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

Лемма. Пусть a и b два фрагмента, а p программа, содержащая вызовы внешней процедуры. Тогда существуют продолжения a' и b' этих фрагментов с таким свойством: ни для каких множеств A и B, согласованных с a' и b', программа p, имея доступ к характеристической функции для B, не будет разрешать множество A.

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

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

Итак, для построения множеств A и B осталось доказать лемму. (К вопросу о 0' -вычислимости мы еще вернемся.)

В формулировку леммы множества A и B входят несимметрично, поэтому и рассуждение будет несимметричное. Фиксируем некоторое число x, которое не входит в область определения фрагмента a, и зададим себе вопрос: существует ли такое множество B, согласованное с фрагментом b, что после присоединения его характеристической функции к программе p эта программа дает на входе x какой-то из ответов " да" и " нет". Если такого множества нет, то вообще заботиться не о чем утверждение леммы будет верным, если просто положить a'=a, b'=b.

Пусть такое множество B существует. Проследим за работой программы p на входе x для этого множества B. Прежде чем выдать свой ответ, программа может некоторое конечное число раз вызывать характеристическую функцию множества B. Возьмем фрагмент b', с которым B согласовано, и притом достаточно длинный, чтобы покрыть и зафиксировать все те места, к которым обращалась программа p. Тогда программа p будет давать тот же самый ответ не только для множества B, но и для любых множеств, согласованных с b'. Остается обеспечить, чтобы этот ответ был неверным, что можно сделать, включив x в область определения a' и выбрав a'(x) противоречащим этому ответу. Лемма доказана.

Осталось лишь доказать утверждение теоремы, относящееся к 0' -вычислимости, для чего надо убедиться, что построение a' и b' в доказательстве леммы можно сделать 0' -алгоритмическим. Ключевой момент здесь ответ на сформулированный при доказательстве леммы вопрос. Конечно, буквально перебрать континуум возможных множеств B, согласованных с фрагментом b, невозможно. Но это и не требуется надо просто просматривать все варианты работы программы p. Когда она задает вопрос про не входящее в b число, просмотр разветвляется на два направления в зависимости от двух возможностей. Получается ветвящееся дерево вариантов, и вопрос состоит в том, получается ли ответ " да" или " нет" хоть на какой-то ветви. А этот вопрос можно переформулировать как вопрос о том, остановится ли некоторая программа (а именно, программа, просматривающая параллельно все ветви и останавливающаяся, как только на одной из них появится ответ " да" или " нет").

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

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

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

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

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

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

Будем называть элементом произвольную пару конечных множеств $$\langle A,B\rangle$$ натуральных чисел. Будем говорить, что элемент $$\langle A', B'\rangle$$ продолжает элемент $$\langleA,B\rangle$$, если $$A \subset A'$$ и $$B \subset B'$$. Мы построим вычислимую последовательность элементов, каждый из которых продолжает предыдущий; в пределе (объединении) они дадут искомые перечислимые несравнимые множества.

Будем называть указанием четверку конечных множеств $$\langle A^+,A^-,B^+,B^-\rangle$$, в которой A+ не пересекается с A- и B+ не пересекается с B-. Слово " указание" объясняется тем, что такие четверки указывают, чего мы хотим от элементов: A+ это числа, которые должны входить в A, а A- числа, которые не должны входить в A ; аналогично для B. Формально, мы говорим, что элемент $$\langleA,B\rangle$$ согласован с указанием $$\langle A^+, A^-, B^+, B^-\rangle$$, если $$A^{+} \subset A$$, $$A^{-} \cap A=\varnothing$$, $$B^{+} \subset B$$, $$B^{-} \cap B=\varnothing$$. Будем говорить, что указание u_2 сильнее указания u1, если всякий элемент, согласованный с u2, согласован и с u1 (то есть каждая из четырех частей указания может только увеличиться).

Пусть $$\alpha (X,Y)$$ произвольное свойство пары множеств $$X,Y \subset N$$. С каждым таким свойством свяжем некоторую игру двух персонажей Руководителя (Р) и Исполнителя (И). Игра происходит так: вначале И предъявляет Р некоторое указание u0 и некоторый элемент e0, согласованный с u0. Мы будем называть их начальным указанием и начальным элементом. (Как мы увидим, в окончательной конструкции руководителей будет несколько, и начальное указание и элемент достаются свеженазначенному руководителю от его предшественников но об этом дальше). Р отвечает некоторым указанием u1, после этого И выбирает согласованный с ним элемент e1, затем Р выбирает u2, И выбирает e2 и так далее (игра продолжается бесконечно). При этом:

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

С другой стороны, мы покажем, что для любого числа выигрышных условий $$\alpha _{i}$$, для которых стратегии можно выбрать вычислимо зависящими от i, можно найти пару перечислимых множеств, удовлетворяющую всем условиям. Именно это последнее рассуждение будет использовать идею " приоритета": у нас будет один исполнитель и счетное число руководителей, которым присвоены разные уровни приоритета (главный, менее главный, еще менее главный и т.д.).

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

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

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

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

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

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

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

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

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

Теперь можно забыть о конкретной природе элементов и указаний и показать, что если есть последовательность выигрышных условий $$\alpha _{1},\alpha _{2}, ..$$., причем выигрышные стратегии для Р вычислимо зависят от i, то есть пара перечислимых множеств, удовлетворяющая всем условиям.

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

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

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

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

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

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

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