7.4. О'-вычисления

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

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

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

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

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

< : ж I—>- Нт Т(х, п).

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

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

Рассмотрим теперь следующий О'-алгоритм вычи­сления предельной функции ^. Получив вход х, мы рас­сматриваем по очереди пары (х, 0), (х, 1),... и для ка­ждой из них проверяем, является ли она стабильной. Как только стабильная пара (х,п) будет обнаружена, значе­ние Т(х,п) выдаётся в качестве результата. Очевидно, описанный О'-алгоритм вычисляет функцию t.

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

1{х) = Нт Т(х, п)

при всех х (и обе части этого равенства определены од­новременно). Прежде всего мы сделаем себе небольшое послабление, разрешив функции Т принимать также и некоторое специальное значение, которое мы будем обо­значать звёздочкой. При этом Нт Т(х, п) = а означает,что при всех достаточно больших п значение Т(х, п) рав­но а (и, в частности, не равно *).

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

Теперь определим функцию Т. По предположению функция I вычисляется некоторой программой р, имею­щей доступ к характеристической функции некоторого перечислимого множества К. Обозначим через Кп ко­нечное подмножество множества К, состоящее из тех его элементов, которые успели обнаружиться за п шагов перечисления множества К. Вычисляя Т(х,п), мы сде­лаем п шагов работы программы р, при этом используя вместо К его конечное приближение Кп. Если за эти п шагов программа р не даст ответа (что может быть по разным причинам — отведённое ей время может быть недостаточно, Кп может отличаться от К, да и вообще функция t па, х может быть не определена), то Т(х, п) = = *. Если же за п шагов программа ответ даст, то этот ответ и будет значением Т(х, п) (за одним исключением, о котором мы скажем позже).

Попробуем доказать, что 1(х) = Нт Т(х,п). Пусть

73. —>- СО

1(х) равно некоторому а. Тогда работа программы р (с правильным оракулом К) через некоторое время завер­шается и даёт ответ а. При этом вычислении использует­ся лишь конечное число вопросов к оракулу. Поэтому при достаточно большом п множество Кп в этих местах уже будет совпадать с К. Увеличив п ещё, если надо (чтобы оно превзошло время работы программы р), мы можем гарантировать, что при этом п и при всех больших п значение Т(х, п) будет равно а.

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

Чтобы справиться с этой трудностью, изменим опре­деление функции Т. А именно, договоримся, что если при вычислении Т(х,п) и Т(х,п — 1) протоколы обра­щений к оракулу были разными (задавались разные во­просы или были получены разные ответы на одинаковые вопросы), то Т(х,п) = Это не портит нашего преды­дущего рассуждения, поскольку там при болыпйх п за­даваемые вопросы и даваемые ответы такие же, как в «настоящем» вычислении. Зато теперь мы можем быть уверены, что если последовательность Т(х, 0), Т(х, 1),... имеет предел, то и 1(х) определено. В самом деле, если она имеет предел, то содержит конечное число звёздо­чек. Значит, при всех достаточно больших п оракулу за­даются одни и те же вопросы и получаются одни и те же ответы. Значит, эти ответы правильны, так как в пре­деле Кп стремится к К. Поэтому настоящее вычисление также завершается (с тем же ответом). >

60. Приведённое в задаче 14 (с. 16) определение вычисли­мого действительного числа можно релятивизовать относи­тельного любого множества А. Покажите, что число а явля­ется О'-вычислимым тогда и только тогда, когда оно является пределом вычислимой последовательности рациональных чи­сел.