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

Можно, впрочем, задать и иной вопрос. Предположим, что новая теория квантовой гравитации действительно окажется невычислимой теорией — в том, в частности, смысле, что она позволит нам сконструировать физическое устройство, способное решить проблему остановки. Будет ли этого достаточно для разрешения всех проблем, порожденных нашими размышлениями о доказательстве Гёделя—Тьюринга в первой части книги? Как ни удивительно, ответ — нет!

Попробуем разобраться, почему способность решить проблему остановки ничем нам не поможет. В 1939 году Тьюринг предложил одну важную концепцию, имеющую к этому вопросу самое непосредственное отношение, — концепцию оракула. Идея такова: оракул есть нечто (предположительно, воображаемый объект, существующий лишь в голове самого Тьюринга и вовсе не обязательно реализуемый физически), что действительно может решить проблему остановки. Так, если дать оракулу пару натуральных чисел q и n, то он через некоторое конечное время выдаст нам ответ ДА или НЕТ, в зависимости от того, завершится в конце концов вычисление Cq (n) или нет (см. §2.5). В §2.5 мы доказываем вывод Тьюринга о том, что такой оракул, действующий исключительно вычислительными методами, создать невозможно, однако там ничего не говорится о том, что оракул невозможно построить физически. Чтобы прийти к такому выводу, мы должны твердо знать, что физические законы являются по своей природе вычислительными — а мы этого не знаем, о чем, собственно, и идет, главным образом, речь во второй части. Следует также отметить, что физическая возможность создания оракула не является, насколько я могу судить, следствием из той точки зрения, которую я здесь отстаиваю. Как уже упоминалось, никто не требует, чтобы все проблемы остановки были доступны человеческому пониманию и проницательности, поэтому нет никаких оснований и полагать, что некое физически реализуемое устройство непременно справится со всеми этими проблемами своей физической реализуемости.

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

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

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

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

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

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

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

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

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

Нисколько не сомневаюсь, что найдутся читатели, которые скажут, что вот уж тут-то мои рассуждения окончательно растеряли последние крохи правдоподобия, которые в них еще оставались! И, разумеется, такие чувства вполне понятны. Непонятно лишь нежелание хотя бы ознакомиться со всеми доказательствами, которые я уже в подробностях приводил ранее. Нужно просто вновь пройти по всем доказательствам в главах 2 и 3, заменяя в них машины Тьюринга на машины с оракулом α -го порядка. Не думаю, что такая замена как-то существенно повлияет на суть этих доказательств, но меня, если честно, приводит в содрогание перспектива только ради нее повторять их здесь заново. Следует, впрочем, указать на еще одно обстоятельство: нет никакой необходимости в том, чтобы человеческое понимание приобрело ту же мощь, что и какая угодно машина с оракулом. Как было отмечено выше, вывод G вовсе не обязательно предполагает, что человеческого понимания, в принципе, достаточно для того, чтобы решить любой конкретный случай проблемы остановки. Таким образом, все это не означает, что искомые физические законы в принципе должны непременно оказаться, более общими, нежели те, которыми описываются машины с оракулом любого вычислимого уровня (или хотя бы первого). Нам нужно лишь отыскать нечто, не являющееся эквивалентом любой конкретной машины с оракулом (включая сюда и машины с оракулом нулевого уровня, т.е. собственно машины Тьюринга). Возможно, эти физические законы опишут нечто просто-напросто иное.