7.9. Машины с оракулом и физические законы 579

по своей природе вычислительными - а мы этого не знаем, о чем, собственно, и идет, главным образом, речь во второй части. Следует также отметить, что физическая возможность создания оракула не является, насколько я могу судить, следствием из той точки зрения, которую я здесь отстаиваю. Как уже упоминалось, никто не требует, чтобы все проблемы остановки были доступны человеческому пониманию и проницательности, поэтому нет никаких оснований и полагать, что некое физически реализуемое устройство непременно справится со всеми этими проблемами своей физической реализуемости.

В дальнейшем обсуждении Тьюринг рассмотрел модификацию понятия вычислимости, когда оракула можно вызвать на любом желаемом этапе вычисления. Таким образом, машина с оракулом (выполняющим оракул-алгоритм) представляет собой самую обыкновенную машину Тьюринга, только к ее стандартным вычислительным операциям добавлена еще одна: "Вызвать оракул и спросить у него, завершается ли вычисление Cq (n); по получении ответа продолжать вычисление, учитывая полученный ответ". Оракул можно вызывать снова и снова, если появляется такая необходимость. Отметим, что машина с оракулом является точно таким же детерминированным объектом, как и обычная машина Тьюринга (это для иллюстрации того факта, что вычислимость и детерминизм суть совершенно разные вещи). В принципе, вселенная, которая функционирует детерминирование как машина с оракулом, точно так же возможна, как и вселенная, которая функционирует детерминированно как машина Тьюринга. ("Игрушечные вселенные", описанные в § 1.9 и в НРК, на с. 170, представляют собой, по сути, вселенные-машины-с-оракулом.)

Может ли оказаться так, что и наша собственная Вселенная функционирует как машина с оракулом? Любопытно, что с помощью приведенных в первой части книги аргументов оракул-машинная модель математического понимания "развенчивается" столь же успешно, как и аналогичная модель на основе машины Тьюринга, причем изменений почти не требуется. Нужно всего лишь взять доказательство из § 2.5 и условиться, что запись ".Cq (n)" обозначает теперь "выполнение машиной с оракулом действия над натуральным числом п". Впрочем, лучше ввести другое обозначение, скажем, C'q (n). Как и в случае обычных машин Тьюринга, мы можем составить (вычислимым образом) пронумерованный список машин с оракулом. Что касается

37*

580 Глава 7

их спецификаций, единственной дополнительной особенностью является то, что мы должны, помимо прочего, учитывать, на каких этапах вычисления вызывается оракул; никакой новой проблемы такой учет не составит. Далее мы заменяем алгоритм A (q, n) из § 2.5 оракул-алгоритмом , который, в соответствии

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

Для установления математической истины математики не применяют заведомо обоснованные оракул-алгоритмы.

Отсюда следует неутешительное заключение: физический процесс, функционирующий как машина с оракулом, наших проблем также не решит.

Вообще говоря, весь процесс можно повторить, применив его к "машинам с оракулом второго порядка", которым позволяется вызывать при необходимости оракул второго порядка - который способен установить, завершится работа обычной машины с оракулом или нет. Как и в предыдущем случае, приходим к выводу:

Для установления математической истины математики не применяют заведомо обоснованные оракул-алгоритмы второго порядка.

Очевидно, что этот процесс можно повторять снова и снова - подобно многократной гёделизации, описанной нами в связи с возражением Q19. Для каждого рекурсивного (вычислимого) ординала а вводится концепция машины с оракулом -го порядка, и мы снова получаем все тот же вывод:

Для установления математической истины математики не применяют заведомо обоснованные оракул-алгоритмы а-го порядка, где а - любой вычислимый ординал.

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