Рис. 7.14. Двухмерные замкнутые поверхности, которые можно классифицировать численно (грубо говоря, путем подсчета количества «ручек»). Четырехмерные же замкнутые «поверхности» численно классифицировать невозможно.
Существует множество других классов математических задач, которые неразрешимы численно. Две из них — десятую проблему Гильберта и задачу о замощении — мы обсуждали в §1.9. Еще один пример — задачу со словами (для полугрупп) — можно найти в НРК, с. 130-132.
Следует пояснить, что термин «численно неразрешимый» не означает, что в данном классе имеются отдельные задачи, которые невозможно решить в принципе. Он означает лишь то, что не существует систематического (алгоритмического) способа решить все задачи этого класса. В том или ином отдельном случае порой оказывается возможным получить решение благодаря человеческой находчивости и проницательности, подкрепленной, может быть, некоторыми вычислениями. Может, напротив, случиться и так, что решение каких-то задач из класса окажется человеку не по силам (даже если он возьмет в помощники машину). Похоже, никто об этом феномене ничего определенного не знает, поэтому каждый волен составлять обо всем этом свое собственное мнение. Впрочем, как вполне недвусмысленнопоказывает «гёделевско-тьюринговское» рассуждение из §2.5(вкупе с аргументацией главы 3), задачи таких классов, доступные человеческому пониманию и проницательности (подкрепленным вычислениями, если хотите), все равно образуют класс, который численно неразрешим. (Для проблемы остановки, например, в §2.5показано, что класс вычислений, незавершаемость которых в состоянии установить человек, невозможно охватить каким-либо познаваемо обоснованным алгоритмом A— а от этого уже отталкиваются аргументы главы 3.)
Что касается Героха, Хартла и квантовой гравитации, то проблема эквивалентности четырехмерных многообразий проникла в их анализ постольку, поскольку, согласно стандартнымправилам квантовой теории, квантово-гравитационное состояние предполагает суперпозиции (с комплексными весовыми коэффициентами) всех возможных геометрий — пространственно-временных, в данном случае, геометрий, т.е. четырехмерных объектов. Для того чтобы понять, как определять такие суперпозиции каким-либо уникальным образом (во избежание путаницы при подсчете), необходимо знать, какие пространства-времена считать различными, а какие — одинаковыми. Проблема топологической эквивалентности представляет собой, таким образом, лишь часть более обширной задачи.
Читатель спросит: если вдруг подход Героха—Хартла к квантовой гравитации окажется физически корректным, будет ли это означать, что эволюция физических систем включает в себя нечто существенно невычислимое? Вряд ли на этот вопрос можно дать ясный и однозначный ответ. Мне не ясно даже, так ли непременно из численной неразрешимости проблемы топологической эквивалентности следует неразрешимость более полной проблемы геометрической эквивалентности. Мне не ясно также, какое отношение этот подход может иметь (если вообще может) к искомой объективной редукции, которая предполагает изменения в самой структуре собственно квантовой теории, связанные с необходимостью учета гравитационных эффектов. Тем не менее, работа Героха—Хартла и в самом деле вполне определенно указывает на то, что невычислимость может-таки сыграть свою роль в окончательной, физически корректной теории квантовой гравитации.
7.9. Машины с оракулом и физические законы
Можно, впрочем, задать и иной вопрос. Предположим, что новая теория квантовой гравитации действительно окажется невычислимой теорией — в том, в частности, смысле, что она позволит нам сконструировать физическое устройство, способное решить проблему остановки. Будет ли этого достаточно для разрешения всех проблем, порожденных нашими размышлениями о доказательстве Гёделя—Тьюринга в первой части книги? Как ни удивительно, ответ — нет!
Попробуем разобраться, почему способность решить проблему остановки ничем нам не поможет. В 1939 году Тьюринг предложил одну важную концепцию, имеющую к этому вопросу самое непосредственное отношение, — концепцию оракула. Идея такова: оракул есть нечто (предположительно, воображаемый объект, существующий лишь в голове самого Тьюринга и вовсе не обязательно реализуемый физически), что действительно может решить проблему остановки. Так, если дать оракулу пару натуральных чисел qи n, то он через некоторое конечное время выдаст нам ответ ДАили НЕТ, в зависимости от того, завершится в конце концов вычисление C q( n) или нет (см. §2.5). В §2.5мы доказываем вывод Тьюринга о том, что такой оракул, действующий исключительно вычислительными методами, создать невозможно, однако там ничего не говорится о том, что оракул невозможно построить физически. Чтобы прийти к такому выводу, мы должны твердо знать, что физические законы являются по своей природе вычислительными — а мы этого не знаем, о чем, собственно, и идет, главным образом, речь во второй части. Следует также отметить, что физическая возможность создания оракула не является, насколько я могу судить, следствием из той точки зрения, которую я здесь отстаиваю. Как уже упоминалось, никто не требует, чтобы все проблемы остановки были доступны человеческому пониманию и проницательности, поэтому нет никаких оснований и полагать, что некое физически реализуемое устройство непременно справится со всеми этими проблемами своей физической реализуемости.
В дальнейшем обсуждении Тьюринг рассмотрел модификацию понятия вычислимости, когда оракула можно вызвать на любом желаемом этапе вычисления. Таким образом, машина с оракулом(выполняющим оракул-алгоритм) представляет собой самую обыкновенную машину Тьюринга, только к ее стандартным вычислительным операциям добавлена еще одна: «Вызвать оракул и спросить у него, завершается ли вычисление C q( n); по получении ответа продолжать вычисление, учитывая полученный ответ». Оракул можно вызывать снова и снова, если появляется такая необходимость. Отметим, что машина с оракулом является точно таким же детерминированным объектом, как и обычная машина Тьюринга (это для иллюстрации того факта, что вычислимость и детерминизм суть совершенно разные вещи). В принципе, вселенная, которая функционирует детерминированно как машина с оракулом, точно так же возможна, как и вселенная, которая функционирует детерминированно как машина Тьюринга. («Игрушечные вселенные», описанные в §1.9и в НРК, на с. 170, представляют собой, по сути, вселенные-машины-с-оракулом.)
Может ли оказаться так, что и наша собственная Вселенная функционирует как машина с оракулом? Любопытно, что с помощью приведенных в первой части книги аргументов оракул-машинная модель математического понимания «развенчивается» столь же успешно, как и аналогичная модель на основе машины Тьюринга, причем изменений почти не требуется. Нужно всего лишь взять доказательство из §2.5и условиться, что запись « C q( n)» обозначает теперь «выполнение q-й машиной с оракулом действия над натуральным числом n». Впрочем, лучше ввести другое обозначение, скажем, C' q ( n). Как и в случае обычных машин Тьюринга, мы можем составить (вычислимым образом) пронумерованный список машин с оракулом. Что касается их спецификаций, единственной дополнительной особенностью является то, что мы должны, помимо прочего, учитывать, на каких этапах вычисления вызывается оракул; никакой новой проблемы такой учет не составит. Далее мы заменяем алгоритм A( q, n) из §2.5 оракул-алгоритмом A'( q, n), который, в соответствии с исходным допущением, олицетворяет собой всю совокупность доступных человеческому пониманию и человеческой проницательности средств, необходимых для однозначного установления факта незавершаемости операции C' q ( n) оракула. В точности повторяя доказательство, приходим к следующему выводу:
