Поэтому «невычислимость» каких-то аспектов сознания (в частности, связанных с математическим пониманием) может служить, на мой взгляд, достаточно убедительным доказательством невычислимой природы всех процессов познания.
Что, в сущности, я подразумеваю под термином «невычислимость»? Я уже много говорил об этом, и мне хочется привести еще один конкретный пример, демонстрирующий невычислимость в моем понимании. Для этого я опишу некоторую игрушечную модель вселенной типа тех, которые изобретают физики, когда не могут найти себе лучшего занятия (вообще говоря, это не худшее занятие, которое можно придумать). Эта модель отражает некоторые особенности Вселенной, однако ее не следует, естественно, соотносить с реальной Вселенной. Роль этой скромной модели сводится лишь к иллюстрации некоторых, совершенно определенных характеристик.
В такой модели рассматриваются лишь дискретные моменты времени (мы можем обозначить их просто 0, 1, 2, 3, 4, ...), каждому из которых соответствует некоторое состояние Вселенной, описываемое некоторым набором так называемых полиомино. Вы, естественно, вправе спросить меня, что означает этот новый термин? Полиомино представляет собой просто некий набор квадратиков, способных заполнять плоскость, объединяясь друг с другом (рис. 3.10). Меня сейчас интересуют наборы таких полиомино. Состояние вселенной в предлагаемой игрушечной модели задается только двумя реальными и конечными наборами полиомино. На рис. 3.10 приведены все возможные конечные множества полиомино, перечисленные в соответствии с некоторой вычислительной процедурой S, S1, S2, ... Как выглядит динамика или эволюция этой забавной игрушечной вселенной? Ее развитие начинается в некоторый начальный момент времени с набора полиомино (S, S), а затем продолжается в виде все новых пар множеств полиомино, отбираемых по некоторому заданному правилу. В соответствии с правилом отбора учитываются только такие наборы плиток полиомино, которые позволяют заполнить плоскость целиком. Отбор, следовательно, сводится лишь к решению следующей задачи: можно ли заполнить плоскость плитками заданного набора таким образом, чтобы на плоскости не было «зазоров» или «накладок»? Предположим далее, что в некоторый момент времени наша игрушечная вселенная свелась к двум конкретным наборам полиомино (Sq, Sr), определяющим всю дальнейшую эволюцию данной модели. Если вы можете покрыть всю плоскость набором полиомино Sq, то вы переходите к следующему полиомино (Sq+1, т.е. получаете для следующего момента времени пару множеств (Sq+1, Sr). Если же вам это не удается, вы должны поменять наборы местами, что дает вам новую пару (Sr, Sq+1). Чем нам может быть интересна эта очень простая и даже несколько примитивная модель? Суть рассматриваемой модели в том, что хотя ее эволюция носит совершенно детерминистический характер (ведь выше я задал абсолютно ясную и полностью определенную процедуру развития), она не является вычислимой. Дело в том, что Робертом Бергером была доказана теорема, в соответствии с которой не существуют компьютерные операции, позволяющие моделировать развитие этой вселенной, поскольку можно строго показать, что не существуют алгоритмы, позволяющие решить задачу о заполнении плоскости набором полиомино.
Рис. 3.10. Невычисляемая, но детерминистическая игрушечная модель вселенной, различные состояния которой задаются парой конечных наборов полиомино.
Если первый заполняет плоскость целиком, то временная эволюция осуществляется следующим образом: численный номер первого набора возрастает на единицу, а второй набор используется для «обозначения времени». Если же первый набор не покрывает плоскость целиком, наборы следует поменять местами и продолжить операцию. Эволюция системы, описываемая парой таких наборов полиомино, должна выглядеть следующим образом:
(S, S), (S, S1), (S1, S1), (S2, S1), (S3, S1), (S4, S1), ..., (S278, S251), (S251, S279), (S252, S279), ...
Рассмотренная модель наглядно демонстрирует различие между вычислимостью и детерминизмом. На рис. 3.11 приведены некоторые примеры заполнения плоскости плитками полиомино различных размеров и форм. Легко видеть, что в случаях а и б полное заполнение плоскости осуществляется без труда. В случае в два типа плиток по отдельности не могут заполнить плоскость целиком (на рисунке указаны неизбежно возникающие «зазоры», или «дырки», в покрытии, однако вместе они легко заполняют плоскость). В случае г плоскость можно заполнить плитками одного типа, однако это достигается только за счет достаточно сложной «подгонки».
Рис. 3.11.
Покрытие бесконечной евклидовой плоскости различными наборами плиток полиомино (разрешено также использование зеркальных «отражений» этих плиток). Ни один из двух типов плиток набора в не может заполнить плоскость целиком.
Задача значительно осложняется при попытке заполнения плоскости плитками полиомино более сложной формы, показанными на рис. 3.12 (именно к этой ситуации относится теорема Роберта Бергера). Дело в том, что три типа показанных на рисунке плиток покрывают плоскость целиком, однако эту операцию нельзя осуществить таким образом, чтобы узор повторялся! На каждом этапе процесс заполнения определяется вашим выбором продолжения, в результате чего очень трудно установить порядок действий. Тем не менее операция, безусловно, выполнима, и именно существование таких вариантов заполнения плоскости привело Бергера к формулировке теоремы, из которой следует, что для моделирования развития даже этой игрушечной вселенной невозможно выработать вычислительную программу.
Рис. 3.12. Набор из трех типов плиток полиомино может заполнить плоскость целиком, но заполняющий узор не обладает периодичностью.
А как обстоят дела с описанием настоящей, большой Вселенной? В гл. 2 я уже немало говорил о фундаментальных недостатках существующей физической картины мира. Подумайте, нет ли в физической теории каких-то проблем, заставляющих вспомнить о невычислимости некоторых операций? У меня есть основания считать, что квантовая теория гравитации в своем правильном виде должна быть именно невычислимой. Я говорю об этом вполне серьезно и продемонстрирую вам, что проблема невычислимости возникает, по крайней мере, в двух независимых направлениях развития квантовой гравитации, причем именно тогда, когда мы рассматриваем квантовые суперпозиции четырехмерных пространств-времен (в большинстве существующих теорий используется лишь суперпозиция трехмерных пространственных состояний).
Рассмотрим сначала так называемую схему Героха-Хартля для квантовой гравитации, которая с самого начала содержит элемент невычислимости, поскольку одним из используемых в ней математических положений является доказанная Марковым невозможность вычислительной классификации четырехмерных топологических складок. Я не буду вдаваться в сложные технические детали, но хочу еще раз подчеркнуть, что невычислимость возникает естественным образом при объединении общей теории относительности и квантовой механики.
В качестве второго примера появления невычислимости в теориях квантовой гравитации можно сослаться на результаты, содержащиеся в препринте одной из работ Дэвида Дейча. К моему глубокому удивлению, в полном тексте статьи, опубликованной позднее, я не обнаружил этих данных! Я специально беседовал с автором на эту тему, и он заверил меня, что опустил эти результаты не из-за их ошибочности, а лишь потому, что они были не очень важны для статьи в целом. Он считает, что забавные суперпозиции пространства-времени (которые мы должны рассматривать хотя бы в качестве гипотетически возможных) возникают вследствие того, что некоторые из потенциально возможных вселенных могут образовывать замкнутые пространственно-временные линии (рис. 3.13). В таких ситуациях всякие каузальные (причинно-следственные) связи полностью теряют смысл, причины и следствия «бегут по замкнутому кругу», а прошлое и будущее просто перемешиваются друг с другом. Хотя все это выглядит совершенно нереальным и противофактическим, оно (как и в задаче гл. 2, связанной с испытанием бомб) может влиять на действительные события. Я не считаю эти рассуждения достаточно серьезными и убедительными, однако они показывают, что какие-то невычислимые операции могут легко обнаружиться и в совершенно правильных теоретических построениях.