«Логика – это в первую очередь естественная наука» (Фердинанд Гонсет)

«Либо математика слишком велика для человеческого разума, либо человеческий разум – это нечто большее, чем машина» (Курт Гёдель)

«Достижения Курта Гёделя в современной логике уникальны и монументальны. Определённо, это – нечто большее, нежели памятник ученому, это – путеводная звезда, свет которой продолжит распространяться в пространстве и времени вечно» (Джон фон Нейман)

«Теорема Гёделя быстро получает признание как фундаментальный вклад в основание математики – вероятно, самый фундаментальный из когда-либо найденных» (Роджер Пенроуз)

«Человек никогда не сможет полностью познать себя, поскольку разум может быть уверен в том, что он знает о себе, только полагаясь на то, что он знает о себе. Все ограничительные теоремы математики предполагают, что как только способность представлять свою собственную структуру достигает определённой критической точки, это гарантирует, что человек никогда не сможет представить себя полностью» (Дуглас Хофштадтер)

Учёные доказали: мы не живём в Матрице! В октябре 2025 г. был опубликован доклад о неразрешимости в физике, неалгоритмичности Вселенной и невозможности её полной симуляции, опирающийся на теоремы Гёделя о неполноте. Перевод этой статьи с пояснениями был выполнен уважаемым @Dmytro_Kikot На теоремы Гёделя вообще часто ссылаются, чтобы доказать существование или несуществование Бога, ограниченность научного метода, невыразимость истины словами, непознаваемость мира разумом, невычислимость сознания, неспособность искусственного интеллекта превзойти естественный, невозможность самосовершенствования и т.д. Говорят, эволюционировать, познавать себя и создавать что-то сложнее себя можно только при наличии сверхъестественного источника бесконечной сложности, иначе это превращается в задачу вытащить себя за косичку из болота. Также проводятся параллели со Вторым законом термодинамики, согласно которому энтропия в замкнутой системе не может уменьшаться, а значит, там не будет самоорганизации и упорядоченности. Да и что вообще может рассказать нам наука, если даже математика нелогична, а мир противоречив и парадоксален? Остаётся только уповать на интуицию, которая якобы неалгоритмична и является откровением самой Истины, снисходящей лишь до тех, кто достоин. А может, мы просто неправильно понимаем теоремы Гёделя? Давайте разбираться, каковы следствия этих теорем для физики, информатики и философии, возможна ли алгоритмическая теория всего, и накладывает ли неполнота Гёделя ограничения на то, что мы можем познать своим разумом.

Теоремы Гёделя о неполноте и парадоксы самореференции

Начнём с того, что любая формальная система, будь то математика, физическая теория, язык программирования или ментальная модель – это способ упростить и сократить реальность, чтобы сделать её доступной для понимания нашим ограниченным в вычислительных ресурсах мозгом или компьютером. Математику можно представить как дерево, вырастающее из семени (аксиомы) путём применения одних и тех же правил вывода, позволяющих создавать новые элементы из предыдущих. Этот процесс называется рекурсивным определением: из аксиом вырастают теоремы первого поколения, из них вырастают теоремы второго поколения, и т.д. Например, из семян 1 и 2 с помощью правила F_n = F_{(n – 1)} + F_{(n – 2)} вырастает последовательность Фибоначчи, лежащая в основе золотого сечения, а случайная на первый взгляд последовательность простых чисел в спиральном представлении на квадратной решётке образует скатерть Улама. Каждая рекурсивно определённая последовательность битов имеет повторяющиеся паттерны, которые можно закодировать в виде правила и тем самым сжать строку. На этом основано всё программирование. Если же такие паттерны отсутствуют, последовательность нерекурсивна, т.е. представляет собой случайный набор битов, и сжать её невозможно. Вычислимость и рекурсивность – эквивалентные понятия.

Если представить мир как очень длинную (возможно, бесконечную) строку битов, то задача науки сводится к поиску в ней однотипных повторяющихся участков и кодированию этих паттернов с помощью коротких рекурсивных (обращающихся к себе) правил. Вселенная по природе своей самоподобна и вычислима, иначе наука, математика и программирование были бы невозможны, как невозможно сжать абсолютно случайную строку битов. Но вычислима ли она в полной мере, как идеальный фрактал, или некоторые её части всё равно останутся несократимыми, какую бы формальную систему мы ни использовали?

В начале XX века математик Давид Гильберт, автор знаменитого лозунга «Мы должны знать, мы будем знать», поставил три условия, которым должна соответствовать формальная система: непротиворечивость (из одних и тех же аксиом нельзя вывести два противоречащих друг другу утверждения), полнота (все математические утверждения должны быть либо доказуемо истинными, либо доказуемо ложными) и разрешимость (существование однозначной механической процедуры определения истинности или ложности любого математического утверждения).

Самым важным требованием была непротиворечивость, поскольку доказуемость одного-единственного противоречия означает, что становится доказуемым любое утверждение – происходит дедуктивный взрыв. То есть срабатывает закон Дунса Скота (Закон отрицания антецедента): «из лжи следует что угодно». Второе требование – полнота, сводится к формуле, которую Дуглас Хофштадтер называет «кредом математика»: «утверждение истинно, когда у него есть доказательство, и утверждение ложно, когда у него нет доказательства». Если доказательство не гарантирует истинность, это высмеивает саму идею доказательства, а если истинность недоказуема, это означало бы существование внутри математики закономерностей без причин. Следовательно, истинность и доказуемость – это одно и то же, равно как ложность и недоказуемость. Третье условие – разрешимость, предполагало существование единого алгоритма доказательства любой теоремы, нахождение которого было основной целью программы Гильберта по формализации математики. Гильберт рассматривал доказательство как конечную логическую цепочку перестановок символов, он исключал из математики бесконечные доказательства. Программа Гильберта предполагала возможность изучать одну формальную теорию при помощи другой, используя для этого классическую логику и формальную арифметику. Но в 1931 г. Курт Гёдель поставил на этой программе крест, обнаружив фундаментальный предел математики и возможности доказательства теорем.

Согласно первой теореме Гёделя (теореме о неполноте), всякая непротиворечивая аксиоматическая теория содержит утверждения, которые нельзя ни доказать, ни опровергнуть средствами самой этой теории. Согласно второй теореме Гёделя (теореме о противоречивости), непротиворечивость всякой аксиоматической теории не может быть доказана средствами самой этой теории. Например, если формальная арифметика непротиворечива, то в ней существует невыводимая и неопровержимая формула, а её непротиворечивость можно формально доказать только в рамках более сильной метатеории. «Любая… формальная система, способная выразить элементарную арифметику, не может быть одновременно непротиворечивой и полной. В частности, для любой непротиворечивой… формальной системы, доказывающей некоторые базовые арифметические истины, существует арифметическое утверждение, которое является истинным, но теоретически недоказуемым».

Мы уже вкратце разбирали формулировки и смысл теорем Гёделя в статье «Реализм против платонизма», но теперь нам придётся рассмотреть само доказательство первой теоремы Гёделя о неполноте, чтобы лучше понять, о чём же она говорит. На формальном языке доказательство выглядит примерно так:

Но мы дадим более понятное и многословное описание того, что сделал Гёдель. Одно из лучших объяснений доказательства Гёделя приводит Дуглас Хофштадтер в книге «Я – странная петля».

Курт Гёдель выбрал в качестве объекта для деконструкции формальную систему «Принципов математики» (ПМ) Рассела-Уайтхеда – громоздкий трёхтомный труд, в котором доказательство формулы 1+1=2 (на языке ПМ – «s0 + s0 = ss0») занимало 379 страниц. Это был итог программы Готлоба Фреге по выведению всей математики из формальной логики. Главной задачей Бертрана Рассела и Альфреда Норта Уайтхеда было исключить самореференцию и связанные с ней парадоксы, такие как парадокс Рассела: включает ли само себя множество всех множеств, не включающих самих себя? Чтобы ни одно множество не могло включать само себя, они разработали разветвлённую теорию типов, которая позволяла множеству данного типа содержать только элементы более низких типов. Рассел и Уайтхед были уверены в истинности всего, что доказуемо внутри ПМ, и в том, что никакая ложь не доказуема в ПМ.

Для Рассела «Принципы математики» были просто набором бессмысленных знаков, механически переставляя которые по формальным правилам, любая машина смогла бы доказать все математические теоремы. Он надеялся, что все механически произведенные теоремы ПМ будут истинными (т. е. никогда не будет произведено ложное утверждение), и что все истинные утверждения теории чисел будут механически произведены внутри ПМ (т. е. нет такого истинного утверждения, которое никогда не будет произведено). Если бы кто-то доказал в ПМ формулу, выражающую ложное арифметическое утверждение (например, «0 = s0»), ПМ можно было бы отправлять в утиль, поскольку из одного доказанного ложного утверждения по правилам ПМ следовало бы бесконечное число других («1 = 2», «0 = 2», «1 + 1 = 1», «1 + 1 = 3», «2 + 2 = 5» и т.д.), и с помощью ПМ можно было бы доказать вообще что угодно о чём угодно. Но «Принципы математики» превратились в макулатуру по другой причине – из-за публикации Курта Гёделя, доказавшего их неполноту.

В статье «О формально неразрешимых утверждениях “Принципов математики” и схожих систем (I)» Гёдель предложил первый универсальный язык кодирования, основанный на целых числах и позволявший формализовать операции любого цифрового компьютера в аксиоматической форме. Речь идёт о гёделевской нумерации для представления как данных (аксиом и теорем), так и программ вывода (последовательности операций над данными, генерирующие доказательства). Гёдель догадался, что типографские символы ПМ, обозначающие логические выводы новых теорем из предыдущих, могут «отражаться» в арифметике. Например, вывод теоремы Z из теорем X и Y по типографскому правилу R5 соответствует получению числа z из чисел x и y по вычислительному правилу r5. Если x –номер теоремы X, а y – номер теоремы Y, то z чудесным образом окажется номером теоремы Z. С помощью арифметизации синтаксиса доказательство утверждения заменяется проверкой наличия у числа заданного свойства. То есть можно для каждого типографского правила вывода, работающего на строках ПМ, предоставить идеально соответствующее вычислительное правило, работающее на числах.

Гёдель придумал, как сопоставить метаматематические утверждения о системе аксиом с утверждениями о числах, сделанными в рамках самой этой системы. Он присвоил каждому возможному утверждению и последовательности утверждений, независимо от их истинности или ложности, уникальный номер, чтобы впоследствии по этому номеру можно было механически выдать соответствующую строку, разложив его на множители. Базовый алфавит ПМ состоял всего лишь из 12-ти символов:

Числами больше 12 обозначались переменные, начиная с x, y и z.

Как известно, любое натуральное число можно представить в виде произведения простых чисел, причём единственным образом. Идея Гёделя заключалась в том, чтобы в каждой строке символов (формуле) ПМ заменить знаки их кодовыми номерами, а затем использовать эти номера как степени, в которые возводятся последовательно идущие друг за другом простые числа, перемножить эти числа и получить уникальный номер для строки. Например, символы утверждения 0 = 0 кодируются числами 6, 5 и 6. Возводим в соответствующие степени три первых простых числа и перемножаем их: 2⁶ × 3⁵ × 5⁶ = 243 000 000. Это и есть уникальный номер для формулы 0 = 0. Поскольку целые числа можно разложить на множители единственным способом, никакая другая формула не получит такой же номер. Далее Гёдель аналогичным способом пронумеровал последовательности формул – математические доказательства, возводя простые числа в степени, соответствующие номерам этих формул (например, 2^{243 000 000}), и перемножая их. Поскольку простых чисел бесконечно много, закодировать таким образом все возможные комбинации символов ПМ не составит труда, несмотря на астрономичность номеров Гёделя.

Одни числа в кодировке Гёделя соответствуют осмысленным формулам ПМ, пусть даже и ложным («0 + 0 = = sss0»), другие – бессмысленным, грамматически неправильным строкам («=) 0 (=»). Первых будет намного меньше, чем вторых. Правильно построенные формулы делятся на истинные и ложные. Числа, соответствующие истинным утверждениям ПМ, назовём вместе с Хофштадтером «принципиальными», а соответствующие ложным утверждениям – «нахальными». Предположим, что каждой доказуемой строке ПМ соответствует «принципиальное» число, которое после достаточно долгого вычисления может быть расшифровано в символы. Например, число 243 000 000 – принципиальное, потому что формула «0 = 0» правильно построена и выводима внутри ПМ.

Нумерация Гёделя позволяла математическим теоремам ссылаться на самих себя и становиться метаматематическими утверждениями – теоремами о теоремах. Гёдель сформулировал утверждения о вычислении других формальных утверждений, описывающие последовательность действий, в результате которых формируются новые утверждения. Например, «первый символ формулы ~(0 = 0) это тильда» - истинное метаматематическое утверждение, касающееся ложного математического утверждения ~(0 = 0), превращается в утверждение о номере конкретной формулы – а именно, что его первая степень равняется 1, то есть номеру для тильды. Иначе говоря, наше утверждение говорит о том, что в номере 2¹ × 3⁸ × 5⁶ × 7⁵ × 11⁶ × 13⁹ есть только один множитель «2». Теперь для каждого утверждения p можно задать вопрос, является ли число x гёделевым номером его доказательства. Соотношение между гёделевым номером p и x (потенциальным гёделевым номером его доказательства), является арифметическим отношением между двумя числами.

Проблема разрешимости (нем. Entscheidungsproblem) Давида Гильберта требовала найти алгоритм, который принимал бы в качестве входных данных описание формального языка и математического утверждения, и, после конечного числа шагов, останавливался бы и выдавал один из двух ответов: «истина» или «ложь», в зависимости от того, истинно утверждение или ложно. Применительно к ПМ нужно было построить машину, которая будет безошибочно отвечать на вопрос «Является ли n принципиальным числом?», отличая поданные на вход принципиальные числа от нахальных, и соответствующие им истинные утверждения от ложных. Если ответ «да», мы узнаём, что гипотеза N доказуема и потому истинна, если ответ «нет», мы узнаём, что гипотеза N недоказуема и потому ложна. Это наделяло бы принципиальные числа магическим статусом, ведь они решали бы любые математические проблемы. Однако на практике отличить принципиальные числа от «нахальных» невозможно, потому что они не следуют друг за другом по возрастающей и не образуют рекурсивно определимую последовательность.

В завершение своего доказательства Гёдель сформулировал очень длинную строку ПМ, которая заявляла: «число g не является принципиальным числом». Однако число g оказалось числом Гёделя, соответствующим этой самой формуле. То есть формула буквально говорила о себе самой: «эта формула недоказуема по правилам ПМ» или просто «я недоказуема». Более того, Гёдель показал, что она не одна, а есть бесконечное количество таких странных формул вроде «ни я, ни моё отрицание не являются теоремами ПМ», «если я доказуема внутри ПМ, то доказательство моего отрицания короче, чем моё» и т.д.  Но как вообще Гёдель сумел поместить число Гёделя для формулы в саму эту формулу, если это число содержит больше символов, чем сама формула? А дело в том, что некоторые большие числа имеют короткое описание, которое можно вставить в формулу в виде символов. Как если бы мы впихнули в спичечный коробок не слона, а его ДНК-описание. Это похоже на парадокс Берри: предложение «это предложение имеет пять слов» имеет пять слов, но утверждение «наименьшее число, которое не может быть обозначено менее чем 100 символами», которое содержит 74 символа, обозначает число, которое по определению не может быть обозначено менее чем 100 символами.

Как заметил Дуглас Хофштадтер, формула Гёделя аналогично следующему предложению:

«в кавычках перед самим собой образует полное предложение» в кавычках перед самим собой образует полное предложение

Фраза в кавычках совпадает с фразой после них, так же, как число Гёделя служит как номером формулы, так и её частью:

«при передаче собственного числа Гёделя даёт нахальное число» при передаче собственного числа Гёделя даёт нахальное число

Здесь нельзя не вспомнить знаменитый парадокс лжеца. Критянин Эпименид сказал: «Все критяне – лжецы». Или просто: «Это предложение ложно». Если само утверждение истинно, то оно говорит о своей ложности, и, следовательно, оно ложно. Если само утверждение ложно, то ложно, что оно ложно, и, следовательно, оно должно быть истинным. Ответ заключается в том, что утверждение не является ни истинным, ни ложным. Аналогично и Гёдель показал, что существует бесконечно много истинных, но недоказуемых в ПМ утверждений. Формула ПМ заявляет о нахальности своего собственного числа Гёделя, а это означает, что формула на самом деле заявляет о собственной недоказуемости. Так она действительно недоказуема внутри ПМ или нет? Если бы она была доказуемой, это означало бы существование последовательности формул, доказывающих формулу с номером g, которая утверждает, что такого доказательства не существует. Отсюда следует либо одновременная истинность утверждений G и ~G, что делает систему противоречивой, либо ложность G, а никакое ложное утверждение не должно быть доказуемым в системе ПМ. Следовательно, для сохранения непротиворечивости ПМ мы вынуждены признать формулу недоказуемой, о чём она же сама и говорит. Получается, формула истинна, но недоказуема, причём недоказуема она именно потому, что она истинна. Это и есть доказательство первой теоремы Гёделя о неполноте.

Далее Гёделю уже не составило труда доказать методом от противного вторую теорему о неполноте. Он сформулировал на языке ПМ утверждение: «ПМ не может доказать противоречие». Если бы ПМ могла доказать свою непротиворечивость, это означало бы существование построенных из её аксиом формул, доказывающих формулу «ПМ непротиворечива», но тогда, согласно первой теореме о неполноте, система была бы неполна – она включала бы истинные формулы, которые нельзя доказать. И одной из этих формул как назло оказывается наше самореферентное утверждение «ПМ непротиворечива» - оно тоже истинно, но недоказуемо. Следовательно, ПМ не может доказать, что она свободна от противоречий. Нельзя доказать непротиворечивость формальной системы средствами самой системы. Однако непротиворечивость арифметики можно доказать неформально, просто принимая её аксиомы как самоочевидно истинные – а из истинных утверждений не может следовать ложный вывод, который сделал бы арифметику противоречивой. Такое доказательство не может быть записано по правилам теории доказательств Гильберта, поскольку в этих правилах семантика заменена на синтаксис, а истинность – на выводимость. Также возможно индуктивное доказательство: в 1936 г. Герхард Генцен доказал непротиворечивость арифметики, добавив в список аксиом логики первого порядка бесконечные доказательства методом трансфинитной индукции.

Все парадоксы самореференции так или иначе обусловлены смешением уровней иерархии систем. Отсюда можно заключить, что построение более мощной иерархии с чётким разделением её элементов (формул, множеств) на разные типы решает проблему гёделевской неполноты. Но по Гёделю не существует полной формальной теории, где были бы доказуемы все истинные теоремы арифметики. Если мы продолжим расширять формальную систему новыми аксиомами или строить более общие метасистемы, это лишь создаст больше истинных и недоказуемых утверждений. Причём из-за усложнения логического языка проблема непротиворечивости и полноты ещё более усложняется, что приводит к бесконечной логической эскалации по спирали усложнений. Например, аксиома выбора не может быть ни доказана, ни опровергнута в теории множеств Цермело-Френкеля (ZF). Её включили в качестве аксиомы в более мощную систему ZFC, но оказалось, что есть независимая от этой системы гипотеза континуума (Курт Гёдель доказал, что она не может быть опровергнута, а Пол Коэн доказал, что она не может быть доказана).

Как мы выяснили в статье «Фрактальное самоподобие Вселенной», определение границы фрактала – невычислимая задача, потому что эта граница представляет собой бесконечно длинную ломаную линию. Аналогично и в любой формальной аксиоматической системе вроде ПМ нет чёткой, выявляемой границы между истиной и доказуемостью. Если формула является теоремой, она почти наверняка истинна, но если формула не является теоремой, это отнюдь не означает, что она ложна. Разделительная черта между истинными и ложными утверждениями, а также между соответствующими им принципиальными и нахальными числами, невычислима никакими математическими методами. Множество истинных формул арифметики первого порядка (т.е. множество принципиальных чисел при любой фиксированной гёделевской нумерации) не является арифметическим множеством. Отсюда следует, что понятие арифметической истины не может быть выражено средствами самой арифметики. Не существует способа выразить в нотации ПМ утверждение «n является числом Гёделя истинной формулы теории чисел». Об этом говорит теорема Тарского о невыразимости истины, сформулированная и доказанная логиком Альфредом Тарским в 1936 г.

Таким образом, в математике нет «теории всего» - набора исходных аксиом, на основе которых можно доказать каждое истинное утверждение о числах. Не существует абсолютной истины – набор истинных и доказуемых теорем полностью зависит от выбранных аксиом. Ни одна аксиоматика не даёт возможности доказать все математические теоремы. Если продолжить сравнение математики с деревом, с которого мы начали эту главу, то ни одно дерево не заполнит собой всё пространство – между его ветками всё равно остаётся пустота. Можно засеять хоть всю Землю и вырастить настолько высокие и разветвлённые деревья, что их кроны достигнут космоса, но они не заполнят собой всё пространство. Чем больше становится стволов и ветвей (аксиом и теорем) – тем больше войды между ними. Это подозрительно напоминает крупномасштабную структуру вселенной и эвереттическое ветвление Мультивёрса, и сходство отнюдь не случайно. Но мы вернёмся к нему чуть позже.

Проблема остановки и занятой бобёр

Доказательство первой теоремы Гёделя о неполноте фактически является усложнённой версией диагонального метода Кантора, с помощью которого была доказана несчётность континуума и теорема Кантора о том, что множество всех подмножеств всегда мощнее исходного множества. В 1936 г. Алан Тьюринг в статье «О вычислимых числах и их применении к проблеме разрешимости» воспользовался тем же диагональным методом, чтобы доказать свою теорему о неразрешимости проблемы остановки. Он переформулировал задачу разрешимости Гильберта (можно ли отличить доказуемые утверждения в логической системе от опровержимых с помощью механической процедуры) на новом языке теории алгоритмов, предложив математическую модель машины Тьюринга, которая следует механическим правилам для преобразования конечных цепочек символов на бесконечно длинной ленте. Тьюринг показал, что его машина является воплощением формальной системы наподобие ПМ, и что существуют задачи, которые она не может решить. Для тех математических вопросов, на которые можно ответить, существуют эквивалентные компьютерные программы, которые будут работать; для тех же, на которые ответить невозможно, программы работать не будут.

В теории алгоритмов вычисление – это манипуляция информацией/данными. Обычно имеются некие входные данные, которые обрабатываются/преобразуются по определённому алгоритму (программе) для получения выходных данных. В машине Тьюринга каждую комбинацию регистров можно обозначить числом – цепочкой символов. Лента – тоже последовательность символов. Все возможные состояния машины можно поместить в таблицу, пронумеровать и доказать диагональным методом Кантора, что есть состояния, которые не пронумерованы и не входят в список. Доказать или опровергнуть формулу, зашифрованную числом означает просто рассчитать это число. Следовательно, некоторые формулы нельзя доказать или опровергнуть механическим процессом. Тот факт, что рекурсивным функциям можно присвоить гёделевские числа, подразумевает, что существует счётное бесконечное число рекурсивных функций. По теореме Кантора, существует несчётно бесконечное число функций, которые не являются рекурсивными. Им соответствует несчётное число неразрешимых задач. Алгоритмически неразрешимая задача – это такая задача, ответ на которую существует, но для нахождения ответа для каждого нового набора данных приходится фактически изобретать новый метод решения. Алгоритмическая неразрешимость указывает не на невозможность найти решение в принципе, а на невозможность найти общее решение.

Задача остановки спрашивает, будет ли компьютерная программа работать вечно, или в конце концов остановится. Обозначим код программы как p, входные данные как x. Запись p(x) – запуск p на x. Вопрос: существует ли вычислимая функция H(p,x) = {1,если p(x) останавливается, или 0,если p(x) не останавливается, корректная для всех p,x? Предположим, что существует корректный решатель проблемы остановки H. Определим программу D, которая использует H как подпрограмму и ведёт себя наперекор её предсказанию на диагонали (когда вход совпадает с кодом): если H говорит, что p(p) остановится, D зацикливается; если не остановится – D останавливается. Это классическая диагональ: поведение D определяется через предсказание о p на собственном коде. Рассмотрим D(D), т.е. будем использовать в качестве входных данных код самой программы D. Если H(D,D) = 1 (предсказывает «остановится»), то по определению D уходит в бесконечный цикл. Если H(D,D) = 0 (предсказывает «не остановится»), то по определению D немедленно останавливается. В обоих случаях предполагаемая корректность H нарушается на входе (D,D). Следовательно, проблема остановки неразрешима: не существует алгоритма, который для всех пар (p,x) корректно решает задачу остановки. Впрочем, для относительно коротких программ обычно нетрудно понять, остановится она или зациклится.

Можно даже экспериментально найти границы познания и количественно конкретизировать философские открытия Гёделя и Тьюринга, если определить простейшую машину Тьюринга, поведение которой непредсказуемо и неразрешимо в рамках современной математики. Для этого нужно решить задачу занятого бобра (Busy Beaver), предложенную в 1962 г. Тибором Радо в статье «О невычислимых функциях». Задача состоит в том, чтобы найти останавливающуюся программу заданного размера, которая либо выдаёт максимально возможный результат, либо выполняется с наибольшим количеством шагов. То есть мы берём все машины Тьюринга с определённым количеством состояний, исключаем те, которые работают бесконечно (зацикливаются), а среди оставшихся ищем «занятого бобра» - ту, которая проработала дольше всех и оставила на ленте больше всего единиц. Число занятого бобра, или BB(n) – это максимальное количество шагов, которое может сделать машина с n состояниями перед остановкой. Оно растёт с немыслимой скоростью:

BB(1) = 1
BB(2) = 6
BB(3) = 21
BB(4) = 107
BB(5) = 47 176 870
BB(6) – точное значение неизвестно, но недавние расчёты показывают, что для его описания необходимо несколько уровней тетрации (многократного возведения в степень) – порядка 10 с башней из 15-ти десяток (10 ↑↑ 15 в нотации Кнута).

Чем больше правил у машины Тьюринга, тем сложнее становится её поведение и тем сложнее определить, остановится ли она. Алан Тьюринг доказал, что поведение некоторых машин Тьюринга в принципе невозможно предсказать с помощью аксиом ZFC (теории множеств Цермело-Френкеля с аксиомой выбора). Это значит, что начиная с некоторого n значение BB(n) недоказуемо в рамках нашей математики. Насколько велико это n? Доказано, что BB(643) недоказуемо, но предел может оказаться гораздо ближе – не исключено, что уже BB(6) является тем самым «числом Гёделя», значение которого неразрешимо в ZFC, несмотря на его определённость. Если машина Тьюринга с 6 состояниями совершает больше шагов, чем число частиц во Вселенной (~10⁸⁰), то никакой физический компьютер не сможет её симулировать полностью, даже если бы каждая частица была логическим элементом. Никакой эмпирический метод (наблюдение, моделирование, перебор) не даст ответа: остановится она или нет. Никакой человек или алгоритм не сможет предсказать её поведение без решения проблемы остановки. Это означает, что на практике такая машина становится непредсказуемой, несмотря на свою крайне простую структуру: всего 6 состояний, 2 символа, и конечная таблица переходов. Поведение машины определено — она либо остановится, либо нет. Но мы не можем это узнать: знание алгоритма не гарантирует знание результата.

Невычислимая Омега Хайтина

Итак, в 1931 г. Курт Гёдель обнаружил метаматематический предел доказательства, ограничивающий саму идую формализации математики: в любой достаточно богатой формальной системе есть истинные, но недоказуемые утверждения. В 1936 г. Алан Тьюринг конкретизировал неполноту в терминах вычислений: алгоритмы не могут охватить все истины. Нет универсального алгоритма, решающего задачу остановки, иначе мы могли бы обойти неполноту. А в 1975 г. Грегори Хайтин связал неразрешимость с понятием случайности и перевёл её на язык теории информации, изучающей границы сжатия данных и предсказуемости. Он открыл и доказал невычислимость константы Ω (Омега) – вероятности остановки случайной программы на заданном языке. Если бы это число было вычислимым, оно давало бы универсальный ключ к решению неразрешимых математических задач и невычислимых функций. Так, зная первые N бит Ω, можно вычислить проблему остановки для всех программ размером до N. Поскольку многие нерешённые проблемы теории чисел, такие как гипотеза Гольдбаха, эквивалентны решению проблемы остановки для специальных программ (которые, по сути, искали бы контрпримеры и останавливались бы при их нахождении), знание достаточного количества бит константы Хайтина также означало бы знание ответа на эти проблемы. Но поскольку проблема остановки в общем случае неразрешима, вычисление любой константы Хайтина, кроме первых нескольких бит, для универсального языка невозможно. Это превращает сложные проблемы в неразрешимые, подобно попытке построить машину-оракула для задачи остановки.

Хайтин рассмотрел совокупность всех бесконечных последовательностей нулей и единиц – пространство Кантора – как все возможные программы, которые могла бы выполнить машина Тьюринга, а затем оценил вероятность того, что программа, выбранная случайным образом из всех возможных, остановится. Затем он показал, что эта вероятность остановки превращает вопрос Тьюринга об остановке программы в действительное число, находящееся где-то между 0 и 1. Хайтин назвал это число Омега и доказал, что оно невычислимо. Доказательство основано на алгоритме, который, зная первые n цифр числа Ω, решает проблему остановки Тьюринга для программ длины до n. Поскольку проблема остановки неразрешима, число Ω не может быть вычислено. Это отличает его от вычислимых действительных чисел. Например, число Пи можно сгенерировать с помощью относительно короткой программы, которая вычисляет бесконечное количество цифр по одной – насколько далеко вы зайдёте, зависит лишь от времени и ресурсов. Но для числа Омега такой программы не существует: в двоичной системе оно представляет собой бесконечную случайную строку нулей и единиц.

Существует бесконечное множество вероятностей остановки, по одной для каждого языка программирования, но принято использовать букву Ω для обозначения их всех. Каждая константа Хайтина Ω обладает следующими свойствами:

• это нормальное и трансцендентное действительное число, то есть его цифры равномерно распределены, как если бы они были получены подбрасыванием честной монеты;

• она вычислимо перечислима, то есть является пределом вычислимой, возрастающей, сходящейся последовательности рациональных чисел;

• она алгоритмически случайна (случайна по Мартину-Лёфу), то есть кратчайшая программа, выводящая первые n бит Ω, должна иметь размер не менее n − O(1);

• это невычислимое число, то есть не существует вычислимой функции, перечисляющей его двоичное представление, и не существует даже алгоритма, способного надёжно угадать её цифры.

По сути Омега Хайтина содержит в сжатой форме все недоказуемые гёделевские истины и является ключом к решению неразрешимых математических задач. Как мы показали в предыдущей статье «Сверхтьюринговые вычисления и гиперкомпьютеры», достаточно подать Омегу на вход компьютера, чтобы превратить его в гиперкомпьютер, решающий задачу остановки для любой программы, в том числе такой, которая вычисляет ответ на неразрешимый вопрос. Но саму Омегу узнать невозможно, не решив задачу остановки. Согласно теореме Хайтина о неполноте, для каждой непротиворечивой аксиоматической системы натуральных чисел, включая арифметику Пеано, существует константа N, такая, что ни один бит Ω после N-го не может быть равен 1 или 0 в этой системе. Иначе говоря, в этой системе невозможно доказать, что ни одно конкретное число не имеет колмогоровскую сложность, превышающую N.

Хотя Омега и невычислима, первые несколько её битов можно вычислить достаточно коротким алгоритмом, который систематически перечисляет и запускает все возможные программы, и когда одна из них останавливается, её вероятность добавляется к выходу. По истечении конечного времени его выход сходится к первым n битам Ω. Однако существует ещё более случайное число Супер-Омега, которое, как показал Юрген Шмидхубер, невозможно существенно сжать никаким перечисляющим неостановимым алгоритмом. Супер Ω – это вероятность остановки для оракула, знающего Омегу. Аналогичным образом гиперкомпьютер, знающий число Супер-Омега, имеет свою вероятность остановки Гипер-Омега, известную только оракулу третьего порядка, и так до бесконечности. По мнению Хайтина, всё это говорит о том, что существует бесконечное множество математических фактов, но по большей части их невозможно связать объединяющими теоремами. Если математики и находят какие-либо связи между этими фактами, то делают это по чистой случайности. «Большая часть математики истинна без какой-либо особой причины – она истинна случайно». А может, это касается и физики?

Доказательство неалгоритмичности Вселенной

В 2025 г. в журнале Journal of Holography Applications in Physics вышла статья «Последствия неразрешимости в физике для теории всего сущего», в которой профессор Университета Британской Колумбии Мир Файзал и его коллеги из других стран, доктора Лоуренс Краусс, Аршид Шабир и Франческо Марино, математически доказали, что мы не живём в Матрице. Они воспользовались теоремами Гёделя о неполноте, теоремой Тарского о неопределимости и теоретико-информационной неполнотой Хайтина, чтобы формализовать тезис о невозможности создания полностью алгоритмической «теории всего». По мнению авторов, первая теорема Гёделя о неполноте предполагает существование корректно сформированных утверждений, которые истинны, но недоказуемы в рамках алгоритмического аппарата квантовой гравитации, а вторая теорема не позволяет вычислительной теории всего доказать собственную самосогласованность. Физически неразрешимым предложениям Гёделя соответствуют эмпирически значимые факты, например, конкретные микросостояния чёрных дыр, которые остаются за рамками любого конечного вывода, основанного на правилах.

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

«Опираясь на математические теоремы, связанные с неполнотой и неопределимостью, мы демонстрируем, что полностью непротиворечивое и полное описание реальности невозможно достичь только с помощью вычислений. Для этого требуется неалгоритмическое понимание, которое по определению выходит за рамки алгоритмических вычислений и, следовательно, не может быть смоделировано. Следовательно, эта вселенная не может быть симуляцией».

Что же это означает? Вселенная не является ни симуляцией, ни компьютером. Цифровая физика, гипотеза «всё из бита» Джона Уилера, Конечный ансамбль Макса Тегмарка, теория гиперграфов Стивена Вольфрама и другие подобные модели не могут полностью описать реальность. Любая формальная теория квантовой гравитации, в которой пространство-время генерируется алгоритмическими вычислениями на основе конечного набора аксиом и правил вывода, будет заведомо неполной. «Чтобы достичь действительно полной и самосогласованной теории квантовой гравитации, необходимо дополнить формальную модель неалгоритмическими ресурсами – внешними аксиомами предикатов истинности или другими металогическими механизмами, - которые выходят за рамки рекурсивного перечисления, оставаясь при этом эмпирически согласованными с физикой на планковском масштабе». Квантовые измерения, планковские процессы, квантово-гравитационные амплитуды и космологические начальные условия могут стать доступными для принципиального, но невычислимого вывода, гарантируя, что никакая физически значимая истина не останется вне области теоретического понимания.

Вместо вычислительных теорий авторы статьи предлагают «метатеорию всего» (MToE), основанную на «неалгоритмическом понимании». В качестве примеров невычислительных метапринципов они приводят принцип самосогласованности Новикова (логическое ограничение на пространство-время с замкнутыми времениподобными кривыми) и неразрешимую квантовую логику с механизмом коллапса волновой функции. Авторы статьи явно поддерживают теорию объективного гравитационного коллапса Диози-Пенроуза и аргумент Лукаса-Пенроуза о том, что человеческое познание превосходит формальные вычисления и может получить доступ к истинам за пределами формальных доказательств. Согласно гипотезе Orch-OR Хамероффа-Пенроуза, когнитивные процессы используют квантовый коллапс, который порождается предикатом истинности квантовой гравитации, поэтому математики-люди могут постичь гёделевские истины, тогда как компьютеры не могут.

Отмечается, что крах вычислительных описаний природы не влечёт за собой крах науки и не подрывает принцип достаточного основания (каждый истинный факт должен быть основан на адекватном объяснении). Неполнота Гёделя, неопределимость по Тарскому и границы Хайтина не отрицают этого требования; они лишь показывают, что «адекватное объяснение» шире, чем «выводимое конечной механической процедурой». Существование истинных, но недоказуемых предложений квантовой гравитации не означает, что эти факты лишены оснований, а лишь то, что их основания не обязательно должны быть синтаксически закодированы в каком-либо рекурсивно перечислимом наборе аксиом.

Так значит, Вселенная не является компьютером? А как же квантово-вычислительная парадигма «всё из кубита», тезис Чёрча-Тьюринга-Дойча и невозможность гипервычислений? Если ни одна формальная теория не может доказать все истины о Вселенной, не означает ли это, что существуют некие неалгоритмические процессы, которые навсегда останутся вне достижимости наших измерительных приборов и компьютеров? Неужели во Вселенной всё-таки возможны гипервычисления, и наш мозг является гиперкомпьютером? Разве постулат, что мышление человека интуитивно-неалгоритмично, и что ему доступны какие-то истины за пределами репертуара машины Тьюринга, не ставит под сомнение научный метод, потому что есть более эффективный неалгоритмический механизм познания? А если наш мозг всё же ограничен пределом Тьюринга, получается, что он никогда не сможет познать эти неалгоритмические процессы во Вселенной?

Здесь уместно спросить: а применима ли вообще теорема Гёделя к физическим теориям? Иногда говорят, что теоремы Гёделя распространяются только на формальные аксиоматические системы математической логики и правила вывода, использующие логику первого порядка и сформулированные на языке первого порядка. Это значит, что мы можем навешивать кванторы существования и всеобщности только на индивидуальные объекты, но никак не на их классы, функции, отношения и т.д. Но даже аксиоматика Пеано не может быть сформулирована на языке первого порядка, так как включает в себя математическую индукцию. Языки первого порядка настолько ущербны, что ими не могут быть охвачены даже базовые математические понятия вроде натуральных чисел. Тем не менее, теоремы о неполноте применяются к формальным системам, которые достаточно сложны для выражения базовой арифметики: определены натуральные числа, 0, 1, сложение и умножение. Такие формальные системы эквивалентны по мощности машине Тьюринга.

К невычислимой и неалгоритмической модели Вселенной теоремы Гёделя действительно неприменимы, а вот физический принцип Чёрча-Тьюринга-Дойча как раз-таки говорит, что наша Вселенная вычислима и сама является машиной Тьюринга – одним большим квантовым компьютером. Если рассматривать Вселенную как универсальный компьютер, к ней и ко всем её подсистемам будет применим основной вывод Гёделя о невозможности одновременного достижения полноты и непротиворечивости. К тому же есть аналоги неполноты Гёделя для более мощных систем – неразрешимость Тьюринга в теории алгоритмов, невычислимость колмогоровской сложности в теории информации и вычислительная неприводимость в теории клеточных автоматов.

В середине 80-х гг. исследователь клеточных автоматов Стивен Вольфрам выдвинул гипотезу о вычислительных пределах нашей Вселенной – принцип вычислительной эквивалентности (ПВЭ): «Никакая система никогда не сможет выполнять явные вычисления, более сложные, чем те, которые выполняют клеточные автоматы и машины Тьюринга». Этот принцип ограничивает вычислительную мощность предиктора для расчёта поведения физических систем, настолько сложных, что разработка эффективного алгоритма вычисления их эволюции с абсолютной точностью невозможна. Если физическая система вычислительно неприводима, то не существует более короткого процесса, который может предсказать её физическое поведение, чем само её физическое поведение. Мозг человека тоже является вычислительно неприводимой системой, подчнняющейся формальным правилам. Но тогда о каком «неалгоритмическом понимании» может идти речь?

Аргумент Лукаса-Пенроуза и его деконструкция

Курт Гёдель был платоником, верил в объективные математические истины и доказывал с помощью модальной логики существование Бога. В дизъюнктивном суждении «математика слишком велика для человеческого разума» (т.е. существуют математические истины, превосходящие человеческое знание) или «человеческий разум – это нечто большее, чем машина» (т.е. мышление невозможно механизировать) он явно склонялся ко второму, полагая, что доступ к формально неразрешимым истинам даёт математическая интуиция. Алан Тьюринг, напротив, был материалистом, атеистом и механицистом: он считал, что мозг и разум не выходят за рамки механического, поскольку немеханическая интуиция не может быть обусловлена физическим мозгом. В статье «Вычислительные машины и разум» (1950) Тьюринг писал: «Хотя установлено, что существуют ограничения возможностей любой конкретной машины, было лишь без каких-либо доказательств заявлено, что подобные ограничения не применимы к человеческому интеллекту». Для Тьюринга математик – это устройство, которое находит гипотезы и превращают их в теоремы. Однако это не значит, что мышление строго запрограммировано и предсказуемо: мозг настолько сложен, что он просто выходит за рамки своей механической природы, так же, как и компьютер может вести себя непредсказуемо для программиста.

Философ Джон Лукас в статье «Разумы, машины и Гёдель» (1959) и физик Роджер Пенроуз в книге «Новый ум короля» (1989), пытались доказать, что процессы, связанные с работой мозга, сознания и мышления, не поддаются полной формализации и вычислимости, поэтому искусственный интеллект в алгоритмической форме не может обладать сознанием. Существуют истины в математике, которые нельзя доказать в рамках формальной системы, но человек может интуитивно, неформально осознать истинность таких утверждений. Компьютер действует строго логически и не способен определить, истинно или ложно утверждение, если оно выходит за рамки аксиоматики, а такие утверждения, согласно теореме Гёделя, неизбежно имеются. Человек же, столкнувшись с таким логически недоказуемым и неопровержимым утверждением, всегда способен определить его истинность или ложность, исходя из повседневного опыта. То есть способность человека к пониманию и постижению сути вещей невозможно свести к какому бы то ни было набору вычислительных правил и смоделировать на компьютере.

Аргумент Лукаса сводится к следующему. Вычислительные машины по сути являются формальными системами. Гёдель показал, что существуют утверждения, которые невозможно доказать в рамках формальной системы, но люди могут убедиться в их истинности. Следовательно, люди могут делать то, чего не могут компьютеры, а именно распознавать истинность гёделевских утверждений. Аргумент Пенроуза усиливает аргумент Лукаса: человеческое сознание не является алгоритмическим и поэтому не может быть смоделировано с помощью цифрового компьютера типа машины Тьюринга. Согласно Пенроузу, теорема Гёделя была доказана математиками-людьми, несмотря на то, что она же сама запрещает формальной системе доказать свою непротиворечивость. Если математик смог понять значение теоремы и доказать свою неполноту, значит, он не является формальной системой и не используют алгоритм для открытия математических истин, и вычислительная теория разума ложна.

«Неизбежный вывод, по-видимому, таков: математики не используют заведомо обоснованную процедуру вычислений для установления математической истины. Мы приходим к выводу, что математическое понимание – средство, с помощью которого математики приходят к своим выводам относительно математической истины – не может быть сведено к слепому вычислению!» (Роджер Пенроуз)

Пенроуз рассуждает так: если все имеющиеся достоверные знания человечества о неполноте сводятся к компьютерной программе, тогда можно создать самореферентную версию этой программы и вывести противоречие её корректной работе. Следовательно, ни одна программа не может включать в себя всё, что известно людям. Хотя люди могут имитировать машины Тьюринга, машины не могут имитировать всех людей – человеческий разум является сверхтьюринговым. Учёный предположил, что коллапс волновой функции является невычислимым процессом, поскольку выбор состояний не происходит ни случайно, ни алгоритмически. В его теории объективного коллапса состояния выбираются невычислимым влиянием геометрии пространства-времени на планковских масштабах, которая, по мнению Пенроуза, соответствует платоновскому миру чистых идей.

Аргумент Лукаса-Пенроуза неоднократно критиковали другие философы. Так, Хилари Патнэм и Марвин Мински утверждали, что теоремы Гёделя неприменимы к людям, поскольку процесс мышления не ограничивается формальной логикой: люди и нейросети могут считать ложные утверждения верными и совершать ошибки, следовательно, они логически противоречивы и являются непоследовательными машинами Тьюринга. Действительно, люди часто ошибаются, не могут доказать сложные теоремы и не обладают универсальной «интуицией истины». Об этом писал и Мартин Дэвис: «Ни один математик-человек не может претендовать на непогрешимость. Мы все совершаем ошибки!». «В теореме Гёделя нет ничего, что исключало бы эквивалентность математических возможностей человеческого разума алгоритмическому процессу, производящему как ложные, так и истинные утверждения». Чарльз Генри Уайтли в 1962 г. продемонстрировал, что люди подвержены тем же ограничениям, что и машины, предложив аналог недоказуемой гёделевской истины: «Лукас не может последовательно утверждать эту формулу».

Джон Лукас признавал, что, согласно второй теореме Гёделя, человеческий разум не может формально доказать свою непротиворечивость, и даже утверждал, что женщины и политики непоследовательны. Тем не менее, он приводил аргументы в пользу того, почему мужчина, не занимающийся политикой, может считаться непротиворечивым. «Наши противоречия – это ошибки, а не установленные правила. Они соответствуют случайным сбоям в работе машины, а не её нормальной схеме работы». Мы подвержены ошибкам, но не систематически непоследовательны. В противном случае мы бы поверили чему угодно, но склонны отбрасывать противоречия всякий раз, когда их замечаем.

Джон Сёрл полагал, что обращение Лукаса и Пенроуза к Гёделю основано на заблуждении, согласно которому все вычислительные алгоритмы должны поддаваться математическому описанию. В качестве контрпримера Сёрл привёл присвоение номерных знаков (LPN) определённым транспортным средствам с идентификационными номерами (VIN) в ходе регистрации. Никакая математическая функция не может связать известный VIN с его LPN, но сам процесс присвоения довольно прост и осуществляется по принципу «первым пришёл, первым зарегистрирован».

Соломон Феферман утверждал, что математики не доказывают теоремы пошагово, следуя алгоритму механистического поиска доказательств, а рассуждают методом проб и ошибок, озарений и вдохновения. Однако некоторые искусственные машины также способны рассуждать методом проб и ошибок. Действительно, столкнувшись с проблемой, человеческий разум не будет корпеть над ней, применяя один и тот же алгоритм бесконечно, в надежде найти ответ. Механистический подход уместен только после получения начального доказательства для его проверки и подтверждения. Доказательства всегда производятся на более высоких уровнях в виде набросков, а их проверка сегодня осуществляется алгоритмически специальными системами автоматизированного доказательства (Coq, Isabelle, HOL Light). Более того, уже есть нейросети, генерирующие доказательства теорем, которые затем проверяются автоматическими средствами. Так, в 2020 г. в библиотеку Metamath были приняты некоторые доказательства, сгенерированные моделью GPT-f – модификацией GPT-3, обученной на формальном языке Metamath.

Вера в превосходство людей над машинами основана на стереотипе о тупом, холодном и бездушном роботе, который строго следует алгоритму и всегда даёт однозначные запрограммированные ответы. Большие языковые модели разрушили этот миф и показали, что нейросеть может имитировать человеческое мышление со всеми его противоречиями, предвзятостями и когнитивными ошибками. Современные нейросети рассуждают не на основе явных правил и аксиом, а посредством адаптивного статистического распознавания паттернов. Их обучение создаёт не формальные доказательства, а лишь приблизительные соответствия между входными и выходными данными. Нейросеть, обученная на данных, не перечисляет доказательства явно, но всё же реализована на цифровом компьютере, который сам по себе является формальной системой, управляемой вычислимыми правилами. Нейросеть может работать невероятно эффективно, но она не может доказать в рамках своей собственной структуры, почему её результаты истинны или непротиворечивы. Проблема «чёрного ящика» может рассматриваться как неформальное соответствие предела Гёделя. Мы можем проектировать системы, производительность которых выходит за рамки нашего понимания, но не системы, которые сами по себе могут гарантировать, что их выходные данные являются истинным представлением реальности.

В поддержку аргумента Лукаса-Пенроуза можно сказать, что человеческое мышление включает индукцию и абдукцию, которые не сводятся к чистой дедукции. Дедукция – это вывод строго логических следствий из общих посылок. (Все люди смертны; Сократ – человек → Сократ смертен). Она гарантирует истинность вывода при истинных посылках, в противоположность индукции, которая не гарантирует истины. Индукция основана на обобщении опыта от частных случаев к общим закономерностям. (мы видим много белых лебедей и формулируем гипотезу «все лебеди белые»). Также существует метод абдукции, когда выбирается лучшее объяснение для наблюдаемых фактов (врач видит симптомы и предполагает диагноз – это не строгая дедукция, а гипотетическое объяснение). Теоремы Гёделя касаются явных, рекурсивно перечислимых систем дедукции. Индукция и абдукция не подчиняются гёделевским ограничениям, потому что они не требуют строгого доказательства. Большая часть нашего мышления – это эвристики, догадки, вероятностные рассуждения, а не строгие логические выводы. Но если мозг и компьютер являются формальными вычислительными системами, всё мышление должно быть алгоритмическим. Тогда индукция и абдукция – тоже алгоритмы, использующие внешние предикаты истинности.

Все формы мышления (дедукция, индукция, абдукция) должны быть алгоритмически реализуемы. Различие между ними – не в степени механистичности, а в типе алгоритма и в том, какие внешние предикаты или эвристики он использует. Дедукция – чистая формальная процедура внутри формальной системы: проверка посылок → применение правил вывода → вывод. Истинность гарантируется внутренней структурой системы. Индукция – алгоритм обобщения – построение гипотезы на основе конечного множества наблюдений: взять данные → найти закономерность → сформулировать правило. Здесь внешний предикат истинности – статистическая проверка или эмпирическая верификация. Абдукция – алгоритм отбора объяснений: множество возможных гипотез → оценка правдоподобия → выбор лучшей. Здесь внешний предикат – критерий оптимальности (например, минимизация сложности, максимизация вероятности). Абдукция играет ключевую роль в научных открытиях и повседневном мышлении. Её можно моделировать алгоритмически как машинное обучение, байесовский вывод, вероятностные модели, эвристический поиск и т.д., так что это не уникальная человеческая способность.

Пол Бенацерраф в книге «Бог, дьявол и Гёдель» (1967) утверждает, что люди не могут доказать свою непротиворечивость, и показывает, что аргумент Лукаса представляет собой дизъюнкцию: либо ни одна формальная система не кодирует все арифметические способности человека, либо любая система, которая кодирует, не имеет аксиоматики, доступной для понимания человеком. Ссылаясь на Бенацеррафа, Джеффри Лафорте, Патрик К. Дж. Хейс и Кеннет М. Форд предполагают, что человеческий мозг представляет собой непротиворечивые алгоритмы, использующие некую параконсистентную логику, и указывают в качестве примеров на противоречия в трудах самого Пенроуза. В самом деле, чтобы узнать истинность недоказуемого гёделевского предложения, необходимо заранее знать, что формальная система непротиворечива, а это запрещает вторая теорема Гёделя. Чтобы формально доказать, что не всё в человеческом мышлении можно описать формальной системой, нужно сначала формализовать человеческое мышление, иначе не получится сказать о нём что-либо на языке формальной системы. Формальное доказательство того, что мышление невозможно механизировать, предполагало бы, что мышление можно механизировать! Если же человеческое мышление не может быть механизировано, то мы не сможем дать формальную демонстрацию того, что оно не может быть механизировано.

Израильский информатик Нахум Дершовиц отмечает ещё одну ошибку Пенроуза. Предположим, мозг человека вычисляется компьютерной программой. Мы можем использовать формальную математическую систему F для логического вывода поведения P, следовательно, и поведения, убеждений и мыслей H. Таким образом, F инкапсулирует все знания и убеждения H. Пенроуз утверждает: если H верит утверждению X, должно быть возможно доказать X в системе F. Поэтому H будет считать, что система F является корректной, и будет считать, что g истинно. Но, поскольку g не является теоремой F, то F в конечном итоге не может инкапсулировать все убеждения H. Поэтому H не может обладать вычислительным складом ума. Однако теорема Гёделя не говорит, что можно или нельзя доказать относительно состояния ума. Формальная система может не вывести недоказуемое утверждение X, но ничто не мешает ей вывести, что H верит в X. H может в первый день верить в утверждение X, во второй день передумать и поверить в ¬X, а на третий день сойти с ума и поверить в оба утверждения одновременно. Убеждения человека H не являются частью дедуктивной системы F.

Дуглас Хофштадтер утверждает, что в любой достаточно сложной формальной системе, способной к самореференции, возникает рекурсивная «странная петля», которая делает возможной нисходящую причинность, когда обычная иерархия причин и следствий переворачивается с ног на голову. Например, сознание и свобода воли могут быть эмерджентными в том смысле, что требуют объяснений, которые не сводятся к одной лишь физиологии. Нам кажется, что причинность нашего разума лежит на высоком уровне желаний, понятий, мыслей и идей, а не на низком уровне взаимодействий между нейронами или элементарными частицами, хотя, согласно физике, только последние обладают реальной причинной силой и определяют каждое наше решение. Однако может существовать некий высокоуровневый способ понимания, включающий концепции, не встречающиеся на более низких уровнях, и этот уровень может обладать объяснительной силой, которой нет на более низких уровнях. Возможно, недоказуемые гёделевские истины становятся интуитивно постижимыми на высокоуровневом неформальном языке, даже если они невычислимы механически на низкоуровневом языке алгоритмов. Это не значит, что естественный язык лучше описывает реальность, чем язык математики, но он по крайней мере удобнее для описания эмерджентных явлений из области психологии и социологии.

Гипотезу Orch-OR Хамероффа-Пенроуза я уже разоблачал в статье «Гипотезы квантового сознания и критического мозга», повторяться не буду. Мозг – это классический компьютер, поскольку состояния каждого нейрона можно копировать. Состояние нейрона определяется электрическими импульсами (потенциалом действия), проходящими через аксон, открытием ионных каналов, концентрацией натрия и калия, активацией химических или электрических сигналов в синапсах. Эти физические и химические состояния можно измерить и записать напрямую, на них не распространяется квантовая теорема о запрете клонирования. Даже если мозг – недетерминированный аналоговый компьютер, способный решать некоторые задачи эффективнее, чем детерминированный цифровой, он всё равно остаётся формальной системой (например, системой дифференциальных уравнений), не использует невычислимые процессы (например, идеальные непрерывные величины с бесконечной точностью) и не выходит за пределы тьюринговой вычислимости. Понимание – это сжатие: если наблюдения указывают на некую закономерность, их должно быть возможно объяснить с помощью алгоритма, требующего меньшего количества битов, чем количество битов, необходимое для представления наблюдаемых данных. Даже самый случайный набор данных можно «объяснить» с помощью алгоритма того же размера. Но мы интуитивно чувствуем, что понимаем что-то лучше, если это объясняется простой теорией, то есть алгоритмом, требующим меньшего количества битов, чем требуется для описания всего набора данных.

Таким образом, аргумент Лукаса-Пенроуза почти единогласно отвергается философами и научным сообществом как недостаточно обоснованный и логически противоречивый. Заманчиво сделать вывод, что теоремы Гёделя о неполноте доказывают превосходство людей над машинами, поскольку мы способны распознавать истины, которые не может доказать ни один алгоритм. Однако это не более чем утешительная иллюзия. Люди непоследовательны, подвержены ошибкам и зачастую иррациональны, но на уровне отдельных нейронов или элементарных частиц мозг является аналоговым компьютером, ограниченным вычислительными пределами. Также не следует забывать, что мозг человека – открытая система, которая обменивается информацией со средой и модифицирует свою структуру посредством нейропластичности. Мы добавляем новые аксиомы, меняем контексты и используем метафоры и аналогии способами, недоступными фиксированному формализму. Системы ИИ также могут подражать этой гибкости, осваивая новые подходы, а не оставаясь запертыми в рамках одного формального языка.

Самосовершенствование невозможно?

В рамках цифровой физики и квантового панкомпьютерализма, которые мы разбирали в одноимённой статье, логично предположить, что система, которая содержит и поддерживает работу универсальных компьютеров, и сама является универсальным компьютером – одна большая машина Тьюринга вычисляет машины поменьше. Вселенная-компьютер с помощью алгоритмов эволюции сотворила по своему образу и подобию человека-компьютера, который смог достичь вычислительной универсальности и в свою очередь изобрёл универсальный компьютер на кремниевых микросхемах. Как говорил Карл Саган, «мы – это способ, которым Вселенная познаёт саму себя». Но разве теоремы Гёделя не запрещают самопознание и самосовершенствование?

Здесь уместно провести параллель со вторым законом термодинамики, который постулирует неубывание энтропии и как следствие невозможность самопроизвольного упорядочивания изолированной системы. Но он не распространяется на открытые системы, получающие энергию извне и сбрасывающие энтропию в окружающую среду. Аналогично и компьютерная программа, будь то генетический код, человеческое сознание или искусственный интеллект, может эволюционировать только внутри метасистемы. Есть ли такая метасистема у Вселенной – вопрос спорный, но как минимум у неё есть тёмная энергия, замедляющая рост энтропии за счёт ускоренного расширения. А у человечества есть внешний источник ресурсов в виде окружающей среды, загрязняя которую своими отходами, мы обеспечиваем экономический рост и научно-технический прогресс. У отдельных особей есть другие особи и коллективы, а также интернет, с помощью которого можно не только деградировать, но и саморазвиваться. Да, всем известны эти мотивирующие истории о сильных и независимых личностях, которые сделали себя сами и добились успешного успеха без посторонней помощи. Но опытные сапиенсы знают, что объективный самоанализ и самовывоз из болота невозможен, для развития желательно иметь психолога или гуру. Человек не в состоянии познать себя или оценить уровень своего интеллекта, пока не поднимется на следующий уровень сложности, то есть не поумнеет. При этом на новом уровне сложности он сможет понять только себя прошлого, но не настоящего. Всё познаётся в сравнении.

Вот что пишет Дуглас Хофштадтер в книге «Гёдель, Эшер, Бах»:

«Могут ли люди, выйти за пределы самих себя — и могут ли это сделать компьютерные программы? Разумеется, программа может модифицировать себя — но возможность всякой модификации должна быть заложена в программе с самого начала, так что это не может служить примером «выхода из системы». Как бы программа не вертелась и не извивалась, чтобы вырваться за свои пределы, она все же следует заложенным в ней правилам. Она так же не может выйти за пределы самой себя, как человек не может по желанию перестать следовать законам физики. Физика — это система, выхода из которой не существует. Однако возможно осуществить нечто подобное в меньшем масштабе — а именно, выйти из подсистемы собственного мозга в более широкую подсистему. Иногда удается сойти с наезженной колеи. Это всё ещё объясняется взаимодействием различных подсистем мозга, но на вид это весьма похоже на полный выход из себя. Подобно этому, можно представить, что нам удастся создать программу, умеющую частично «вылезать из своей шкуры».

В информатике самосовершенствующаяся программа, использующая эволюционный алгоритм вариации и отбора, называется машиной Дарвина-Гёделя. Её исходная версия, предложенная в 2003 г. Юргеном Шмидхубером – машина Гёделя – представляет собой программу, которая переписывает любую часть своего кода, как только находит доказательства того, что такие изменения полезны. Иначе говоря, машина Гёделя реализует метаобучение: она учится, как следует учиться наиболее оптимальным с точки зрения математики образом, выполняя задачу максимизации ожидаемого в будущем вознаграждения при ограниченной продолжительности жизни. Для этого она системно и эффективно тестирует исчислимые средства доказательства (программы с одобренным результатом), генерируя теоремы до тех пор, пока не находит ту, которая сама доказывает, что предложенные ею изменения действительно полезны, и обещает больше вознаграждений за единицу времени. Разумеется, машина Гёделя не превосходит по репертуару машину Тьюринга. Любой ПК можно сделать автореферентной машиной Гёделя, если просто загрузить в него определённое машиннозависимое ПО, изменяющее собственный код.

Стоп, а как же вторая теорема Гёделя о неполноте, согласно которой ни одна достаточно мощная система не может предоставить доказательство своей непротиворечивости? Разве самосовершенствующийся рекурсивный ИИ не является такой системой? Как же он может математически доказать, что новая версия его кода непротиворечива и безопасна? Действительно, такая проблема есть, и теоретики безопасности ИИ называют её «барьером теоремы Лёба» или «гёделевским препятствием»: самомодифицирующийся интеллект не может полностью подтвердить свою корректность без внешних предположений. Уверенность машины в себе требует либо принятия вероятностных гарантий, либо обращения к метасистемам, непротиворечивость которых также не может быть доказана изнутри. К счастью, барьер можно обойти с помощью эволюционных алгоритмов. Машина Дарвина-Гёделя (DGM) – усовершенствованная версия самообучающейся программы, разработанная японской фирмой Sakana AI вместе с лабораторией Джеффа Клуна из университета Британской Колумбии. Она переписывает свой код не через строгие математические доказательства, а путём естественного отбора среди исходников, которые мутируют, скрещиваются и конкурируют между собой. У неё есть архив исходников, из которого выбирается один или несколько ИИ-агентов (родителей) разной степени успешности, затем с помощью мутаций в коде из них создаются «дети», которые проходят жёсткое тестирование по критерию производительности. Сильнейшие версии программы, превосходящие «родителя» и конкурентов, «выживают» и попадают в архив, чтобы стать родоначальниками новых веток генеалогического дерева ИИ-агентов.

А как насчёт самовоспроизводства? Нет, не размножения – это дело нехитрое, а именно самокопирования, то есть создания своих точных копий? Саморепликация, или способность системы создать копию самой себя – это вполне разрешимая задача по Тьюрингу, связанная с теоремой Клини о рекурсии. Существует машина Тьюринга, которая может вывести своё собственное описание и передать его другой машине или использовать для создания копии. Такие машины называются квазисамореплицирующими – они физически не копируют себя, но алгоритмически воспроизводят своё поведение. Простейшими примерами квазисаморепликации являются клеточный автомат фон Неймана и программа Quine, которая выводит собственный исходный код. Более сложной задачей является создание универсального конструктора – машины, копирующей не только своё описание, но и сам компьютер, на котором работает эта программа. Мы ещё весьма далеки до физической реализации такой машины, но природа построила её максимально приближённый аналог ещё 4 млрд лет назад. Это биологический репликатор – молекула, побуждающая среду её копировать. Каждый живущий на Земле организм содержит в себе гены, которые являются эволюционировавшими потомками той молекулы. Репликаторами являются именно отдельные гены, а не вся ДНК и не целые организмы – мы не клонируем сами себя, хотя на сегодняшний день это исключительно юридическое ограничение.

Тезис Чёрча-Тьюринга-Дойча и неполнота квантовой теории

Итак, мы выяснили, что теорема Гёделя не запрещает одной подсистеме Вселенной (универсальному компьютеру) познавать (моделировать) другую её подсистему (физические объекты). Теперь давайте разберёмся, насколько полным и точным может быть такое моделирование. В предыдущей статье «Сверхтьюринговые вычисления и гиперкомпьютеры» мы выяснили, что машина Тьюринга является самой мощной формальной системой из всех, которые мы когда-либо сможем создать. Она может симулировать любой математический алгоритм, физическое явление или химическую реакцию. Самой мощной вычислительной моделью, реализуемой физически, является универсальный квантовый компьютер. Сверхквантовые гиперкомпьютеры требуют бесконечной памяти, бесконечного времени, бесконечного объёма физического пространства или бесконечной точности измерений – всё это невозможно с учётом нашего текущего понимания физики.

Согласно физическому тезису Чёрча-Тьюринга, всё, что физически вычислимо, может быть смоделировано машиной Тьюринга. В 1985 г. Дэвид Дойч доказал, что универсальный квантовый компьютер может идеально моделировать любую физическую систему с конечномерным пространством состояний. Это значит, что существует программа для каждого физического процесса. Квантовый компьютер является универсальным симулятором квантовой физики, способным эффективно моделировать всё, что описывается уравнением Шрёдингера и его обобщениями, используя суперпозицию и запутанность – молекул, материалов, химических реакций, квантовых полей. Особенность квантового моделирования состоит в том, что модель из кубитов неотличима по всем свойствам и поведению от реального физического объекта, состоящего из атомов. Это значит, что познать объект глубже попросту невозможно – никакими физическими средствами не получится извлечь из него больше информации, чем при измерении на квантовом компьютере. С помощью кубитов можно смоделировать систему настолько точно, насколько это возможно в рамках квантовой теории – более точного алгоритмического устройства не существует. Ни один физический объект не являются кантовской «вещью в себе» со скрытыми от нашего разума свойствами. Благодаря вычислительной универсальности мы можем проникнуть в суть вещей настолько, насколько в принципе позволяет физика.

Как мы выяснили в статье «Вычислительная мощность Вселенной», единственный способ познать Вселенную до конца – это смоделировать её на квантовом компьютере или создать её точную копию до последнего атома. Задача в принципе выполнимая, но потребует не меньше вычислительных ресурсов, чем есть в самой Вселенной. Однако неполнота Гёделя и неразрешимость Тьюринга не запрещают смоделировать любую конечную физическую систему с произвольной точностью, полностью исключив возможные скрытые параметры. О том, как экспериментально исключали скрытые параметры в тестах Белла, я рассказывал в статье «Квантовая случайность против детерминизма». Эти результаты показали, что запутанные кубиты действительно не имеют определённого значения до момента измерения, и что кубиты, приготовленные в одинаковом состоянии, действительно неотличимы, как предсказывает квантовая механика. Чистое состояние кубита – это когда система описывается полным вектором состояния (волновой функцией), и никакой дополнительной информации о ней в принципе узнать невозможно. Теоремы Кохена-Шпеккера и Белла доказывают, что нельзя дополнить квантовую механику скрытыми переменными локального типа, чтобы восстановить классический детерминизм. Они исключают целый класс альтернативных моделей (локальные и неконтекстуальные скрытые переменные), но не исключают нелокальных скрытых параметров (механика Бома) или супердетерминизма. Из них следует, что никакие физические приборы, построенные из обычного барионного вещества, не смогут выявить скрытые параметры: последние либо не существуют, либо принципиально недоступны измерению. Следовательно, их нельзя использовать как ресурс для построения вычислительной модели, более мощной, чем квантовый компьютер. Если бы скрытые параметры были доступны, они могли бы служить оракулом для гипервычислений.

Но почему учёные так уверены в отсутствии скрытых параметров и субквантовых гипервычислений? Ведь теории квантовой гравитации ещё нет, а квантовая теория поля и общая теория относительности остаются математически несовместимыми. В статье «Физика сверхъестественного» я приводил мнение Шона Кэрролла о том, что на бытовых масштабах физика уже изучена вдоль и поперёк, и ничего принципиально нового мы уже не откроем. Мы не знаем окончательной теории всего, но мы можем быть уверены, что она не будет расходиться в предсказаниях с актуальными теориями (КТП и ОТО) на тех скоростях и энергиях, которые сейчас технически доступны. Во Вселенной может быть сколько угодно неизвестных нам частиц, полей, измерений и т.п., но, если они не оказывают никакого влияния на обычное барионное вещество и не могут быть обнаружены экспериментально – говорить о них нет никакого смысла. Об этом пишет и Фрэнк Вильчек в книге «A Beautiful Question»:

«Стандартная модель завершает, для практических целей, анализ материи. Используя её, мы можем вывести, какие виды атомных ядер, атомов, молекул — и звёзд — существуют. И мы можем надежно организовывать поведение больших совокупностей этих элементов, чтобы создавать транзисторы, лазеры или Большой адронный коллайдер. Уравнения СМ были проверены с гораздо большей точностью и в гораздо более экстремальных условиях, чем требуется для применения в химии, биологии, инженерии или астрофизике. Хотя, безусловно, есть много вещей, которые мы не понимаем […] мы понимаем Материю, из которой мы состоим и с которой сталкиваемся в нормальной жизни».

Но если наши теории, включая квантовую механику, заведомо неполны, могут оставаться сверхтьюринговые физические процессы, которые нельзя использовать в качестве вычислительного ресурса. Фундаментальная структура реальности (квантовая гравитация) может включать алгоритмически невыразимые аспекты – «гёделевские истины», которые никакая машина (классическая или квантовая) не вычислит. Возможен сценарий, где квантовая механика даёт максимально полное знание о квантовых системах, а неалгоритмические аспекты проявляются только на более фундаментальном уровне реальности, недоступном приборам и вычислительным моделям. Эти процессы неалгоритмические, поскольку нет конечных мгновенных описаний внутренних состояний, составляющих процесс, или нет способа конечно и точно указать переход от одного мгновенного описания к другому. В таком случае нам пришлось бы признать, что они находятся за пределами нашего понимания, или бесконечно и безнадёжно пытаться подогнать нашу классическую вычислительную модель к такому процессу. Называть их гипервычислительным не совсем корректно, поскольку они физически не доступны (их нельзя использовать для моделирования других процессов) и математически не доступны (не позволяют вычислять математические функции и не имеет конечного математического описания).

Впрочем, даже если некий физический процесс кажется неалгоритмическим, мы никак не сможем это проверить. Например, возьмём палку, длина которой не поддаётся вычислению. В этом случае всё более точные измерения её длины дадут нерекурсивный источник информации, который не может быть смоделирован машиной Тьюринга. Но, как отмечал Леон Бриллюэн, никакое измерение нельзя провести с математически абсолютной точностью: для этого потребуется бесконечное количество энергии. Согласно принципу неопределенности Гейзенберга, определённые пары свойств физических объектов (местоположение и скорость, энергия и время, спин по ортогональным осям) не могут быть одновременно измерены с идеальной точностью. Чем точнее вы измеряете положение частицы, тем меньше вы можете быть уверены в его скорости в тот же момент. Предел точности наших измерений определяется приведённой постоянной Планка, точность которой составляет около 35 знаков после запятой. За пределами этого значения физические свойства вообще не поддаются измерению.

Тоби Орд приводит в качестве примера недоступного для моделирования процесса распад одиночной радиоактивной частицы. Скорость распада частицы не поддаётся вычислению машиной Тьюринга, но этот процесс можно использовать в качестве квантового генератора случайных чисел. Однако, даже если бы у Вселенной был естественный нерекурсивный источник, как мы могли бы быть уверены в его корректности? Проверка бесконечности битов нерекурсивного ресурса потребовала бы той же вычислительной мощности, что и его генерация. Мы можем быть уверены в том, что какой-либо нерекурсивный ресурс действительно нерекурсивен, только если это предполагают наши научные теории. Если во Вселенной действительно существуют невычислимые, неалгоритмические процессы, они могут быть обнаружены косвенно – через наблюдаемые эффекты, которые систематически отклоняются от любых алгоритмических моделей. Их причинная связь с барионным веществом возможна лишь в том случае, если эти процессы проявляются в физических взаимодействиях, доступных эксперименту, но при этом остаются принципиально непредсказуемыми в алгоритмическом смысле. Они могут проявляться как статистические аномалии, влиять на распределение энергии или вероятности событий, флуктуации космического микроволнового фона.

В квантовой механике есть неразрешимые по Тьюрингу задачи: термализация в общей многочастичной модели, реализуемость определённой конфигурация спинов в основном состоянии и другие вопросы, эквивалентные неразрешимым проблемам теории групп и решёток. В 1990 г. Кристофер Мур в статье «Unpredictability and undecidability in dynamical systems» (Physical Review Letters) показал, что даже классические динамические системы могут кодировать задачу остановки. Это означает, что утверждения о долгосрочном поведении системы (например, «система вернётся в исходное состояние») могут быть истинны, но недоказуемы, следовательно, предсказание их поведения в общем случае неразрешимо. Можно сконструировать гамильтониан, чья спектральная структура кодирует задачу остановки для универсальной машины Тьюринга. В частности, Мур спроектировал неразрешимую машину с одной движущейся частью, наподобие пинбольного автомата, которая может имитировать любую машину Тьюринга и вести себя непредсказуемым образом. Вопрос о том, будет ли какая-либо конкретная конфигурация бамперов ловить шарик (что означало бы бесконечное вычисление) или направлять его к выходу (что означало бы конец вычисления), также должен быть неразрешимым.

В 2015 г. Тоби Кубитт, Давид Перец-Гарсия и Майкл Вульф в статье «Неразрешимость спектральной щели» (Nature) доказали, что проблема спектральной щели эквивалентна проблеме остановки: вопрос о том, имеет ли квантовый гамильтониан (оператор энергии) ненулевую щель в спектре, является неразрешимой задачей. Это прямой физический аналог гёделевских утверждений: существуют квантовые системы, для которых невозможно алгоритмически решить, есть ли у них энергетический зазор. Разность энергий между основным и начальным возбуждённым состояниями вещества (сколько энергии требуется, чтобы вытолкнуть систему из её самого низкого энергетического состояния) формально неразрешима, т.е. даже квантовый компьютер не может в общем случае вычислить, будет ли система изолятором или проводником. Это также обусловлено рекурсией: по сути, они кодируют вопросы о спектральных щелях в спектральные щели. Авторы статьи придумали фиктивный квантовый материал, который можно было настроить так, чтобы он действовал как машина Тьюринга: квантовые частицы в сетке атомов выступали в качестве замены ленты, одна из возможных конфигураций суперпозиции представляла начальное состояние машины Тьюринга, другая конфигурация представляла первый этап расчёта, третья представляла второй этап и т.д.

Таким образом, неполнота квантовой теории означает, что существуют вопросы, на которые она не даёт ответа, но это не исключает возможности знать о системе всё, что в принципе доступно знанию, и моделировать её на квантовом компьютере настолько точно, насколько позволяют законы физики. Ни один макроскопический объект не является кантовской «вещью в себе»: можно разложить его на атомы, ввести в когерентное сверхтекучее состояние, смоделировать его свойства на квантовом компьютере и вычислить, как эволюционирует его волновая функция. Но в нём наверняка обнаружатся радиоактивные изотопы, которые распадаются случайным образом и вполне могут послужить триггерами макроскопического хаоса. Последовательность исходов измерений (например, при распаде атомов или прохождении фотонов через поляризатор) может обладать максимальной колмогоровской сложностью – то есть быть невычислимой и нерекурсивной. В копенгагенской интерпретации случайность фундаментальна, поскольку коллапс ВФ нелинеен и необратим. Следовательно, работа квантового генератора случайных чисел алгоритмически невычислима. Искать в сгенерированных им строках скрытый философский смысл или неалгоритмически над ними медитировать бесполезно – из случайной последовательности битов ничего полезного извлечь не получится.

Однако это не означает, что волновая функция неалгоритмична и не подчиняется принципу достаточного основания: её эволюция (уравнение Шрёдингера) строго детерминирована и алгоритмизируема. Результат каждого отдельного измерения случаен и принципиально непредсказуем, но статистика множества измерений вполне вычислима и подчиняется вероятностному распределению Борна. Унитарность квантовой механики – это более строгое условие, чем причинность классического детерминизма. Даже чёрные дыры не могут уничтожить информацию. Но как же так получается, что алгоритмическая унитарная эволюция волновой функции Вселенной приводит к случайностям и неразрешимым проблемам? Примерно так же, как аксиомы и теоремы формальной системы «Принципов математики» приводят к недоказуемым гёделевским истинам.

«Парадоксальная» квантовая логика и квантовая контекстуальность

Распространяется ли теорема Гёделя на квантовую механику и квантовую логику – вопрос дискуссионный. Квантовая механика по своей природе небулева и не обладает самореферентной арифметической структурой, необходимой для построения недоказуемых истин Гёделя. Однако вместо неполноты в квантовой механике возникает контекстуальность, когда результаты измерений зависят от контекста измерения. Квантовая контекстуальность вытекает из теоремы Кохена-Шпеккера, которая показывает, что квантовое измерение не может выявить предсуществующее значение измеряемого свойства независимо от контекста измерения. В своей основополагающей работе «Логика неодновременно разрешимых предложений» (1960) Шпеккер заметил сходство между одновременно неразрешимыми утверждениями квантовой теории и неразрешимостью контрфактуальных предложений. Он проводит аналогию с дискуссиями схоластов вокруг проблемы Infuturabilien: распространяется ли всезнание Бога на контрфактические события, которые произошли бы, если бы произошло что-то, чего не произошло? Молинисты отвечали на этот вопрос отрицательно, совмещая тем самым свободную волю человека с божественным провидением. Небулева логическая структура квантовой теории приводит к аналогичному выводу: либо присваивание значений всем наблюдаемым контекстуально, либо невозможно присвоить предопределённые значения всем наблюдаемым, т.е. эти значения непредсказуемы.

В статье «Проблема квантового измерения» я разбирал мысленный эксперимент «Друг Вигнера» (наблюдатель за наблюдателем) и парадокс Фраухигер-Реннера (наблюдатели за наблюдателями), которые показывают, что «использование квантовой теории, ссылающееся на себя, приводит к противоречивым утверждениям», и что квантовая теория может быть последовательно использована только в метаконтексте. Иначе говоря, вы не можете осмысленно рассуждать о результатах измерений в третьем лице, с позиции другого наблюдателя, теория самосогласована лишь в том случае, если вы применяете её от первого лица. Но это не значит, что вы являетесь единственным наблюдателем во Вселенной, а объективной реальности вообще не существует. Просто наблюдаемые величины, такие как координата, импульс и спин, принимают определённые значения только в контексте измерения, по отношению к измерительному прибору и наблюдателю. Но измерение – это наш способ взаимодействия с волновой функцией, выражающей состояние частицы в комплексных амплитудах. Вектор состояния не сводится к бинарным альтернативам 0 и 1.

Квантовая логика, введённая Джоном фон Нейманом и Гарретом Биркгоффом в 1936 г., отличается от классической логики: она отражает особенности измерений в квантовой механике, где законы распределения истинности не совпадают с булевой алгеброй. В 2016 г. в работе Тобиаса Фрица было доказано, что квантовая логика в гильбертовом пространстве размерности ≥ 3 является неразрешимой по Тьюрингу: не существует алгоритма, который для произвольной формулы квантовой логики мог бы всегда определить, является ли она тождественно истинной. Квантовая теория бросает вызов не только здравому смыслу, но и классической логике, т. е. нашему обычному языку и семантике. В этом смысле квантовая теория более парадоксальна, чем другие физические теории. Но она не настолько парадоксальна, чтобы быть полностью непознаваемой и абсурдной, как преподносят квантовые мистики. Она вполне самосогласована и алгоритмична.

Многие ошибочно понимают квантовую суперпозицию как парадоксальное сочетание противоположностей «и да, и нет», «истина/ложь», «и жив, и мёртв», «и здесь, и там», «0 и 1 одновременно». Сторонники классической логики и скрытых параметров говорят, что так быть не может, и кубит всегда находится в одном из этих двух состояний («0 или 1»), просто наблюдатель не знает, в каком именно. Но на самом деле суперпозиция – это вполне определённое состояние, логически непротиворечивое и точно известное наблюдателю. Дело в том, что между 0 и 1 есть несчётная бесконечность действительных чисел, соответствующих всем возможным состояниям кубита. Кот Шрёдингера тоже может быть живым множеством способов, и быть мёртвым множеством способов, но, в отличие от кубита, не может находиться в промежуточном состоянии. А кубит может, потому что направление его спина или поляризации ничем не ограничено. Наблюдатель выбирает конкретный базис измерения – обычно это вертикальная ось Z – и обозначает направление «вверх» как 0, а направление «вниз» как 1. При измерении кубит всегда переходит в одно из этих синглетных состояний. Но если затем провести измерение по оси X или Y, его результат будет истинно случайным, с вероятностью 50 на 50. Это значит, что состояния «вверх» или «вниз» являются суперпозициями состояний «влево и вправо» и «вперёд и назад». Спин может принимать любое промежуточное значение, не будучи выровненным ни по одной из этих осей. Его состояние всегда определено, но является оно нулём, единицей или суперпозицией, зависит от базиса измерения.

Таким образом, квантовая логика больше похожа не на классическую и не на параконсистентную (противоречивую), а на нечёткую логику, допускающую целый спектр «степени истинности» от 0 до 1. Классическая логика является частным случаем квантовой и справедлива для незначительной части реальности, описываемой классической физикой. Для реализации квантовых алгоритмов нужно небольшое число логических вентилей (гейтов): однокубитные NOT («НЕ», или инверсия по трём осям) и преобразование Адамара (перевод кубита в суперпозицию); двухкубитные CNOT (контролируемое «НЕ») и SWAP (обмен состояниями). Этого достаточно, чтобы реализовать любые алгоритмы – не только классические, но и квантовые. Необратимые логические операции «AND» и «OR» в квантовой логике запрещены, как и операция копирования. Тем не менее, с помощью обратимых квантовых алгоритмов можно выполнить любое классическое вычисление, т.е. симулировать любую машину Тьюринга. Правда, следует помнить, что квантовый компьютер не всегда даёт правильный ответ: он может рассчитать, что 2+2=4, но это не точно, а в другой раз возьмёт и выдаст 2+2=5. Универсальный квантовый компьютер является пусть и вероятностной, но машиной Тьюринга, а значит, на него распространяются теоремы Гёделя и Тьюринга. Точнее, они распространяются на классические результаты измерений – выходные данные – а состояние компьютера в процессе вычисления может быть полным и непротиворечивым. Его можно описывать как единую волновую функцию в представлении Шрёдингера, эволюционирующие во времени операторы в представлении Гейзенберга или как интеграл всех вычислительных путей в представлении Фейнмана.

(Не)полнота и (не)противоречивость Мультивёрса

В «Математических основах квантовой механики» фон Нейман писал, что «наряду с физическими величинами R существует ещё нечто, являющееся предметом физики: именно альтернативные свойства системы L». Т.е. предметом физики являются не только полученные результаты измерений, но и вся совокупность не полученных результатов, которые могли иметь место, но в данном случае не были реализованы. Как же понимать эти не полученные результаты измерений, не говоря уже о не полученных результатах не поставленных экспериментов? Согласно многомировой интерпретации Эверетта, при измерении система не переходит в одно состояние, а разветвляется вместе с наблюдателем: все возможные исходы реализуются в разных ветвях вселенной. Это решает проблему измерения и делает квантовую механику полностью детерминистической на уровне волновой функции. Хью Эверетт рассматривал волновую функцию как универсальное описание реальности, без мистического случайного коллапса. Любое измерение есть не более чем взаимодействие разных компонентов волновой функции Вселенной, при котором все возможные результаты реализуются в соответствующих ветвях. Но вы заранее не можете сказать, какая ваша копия в какой ветви окажется.

В ММИ истинной случайности не существует, как и не существует невычислимых функций и соответствующих им физических процессов. Но как быть с неразрешимыми даже для квантового компьютера задачами? Дело в том, что они так или иначе требует бесконечной точности начальных условий, а квантовая механика это исключает. Классические системы могут быть хаотическими из-за нелинейности уравнения Навье-Стокса: малейшая погрешность входных данных приводит к экспоненциальному изменению результата (эффект бабочки). Но в квантовой механике эффект бабочки отсутствует, поскольку уравнение Шрёдингера линейно: при изменении погрешности входных данных погрешность результата вычислений изменяется линейно. Чтобы предсказать эволюцию системы, нужно просто подставить функцию состояния в уравнение Шрёдингера, и мы получим функцию состояния системы в любой момент времени.

Квантовый компьютер можно рассматривать как полное и непротиворечивое эволюционное уравнение (волновая функция развивается детерминистически по Шрёдингеру). Но гёделевская неполнота проявляется не в самом квантовом компьютере, а в ограниченной перспективе наблюдателя, который после измерения оказывается в одной ветви и имеет доступ лишь к частичной информации. Когда наблюдатель измеряет состояние кубитов, он разветвляется вместе с системой: в каждой ветви фиксируется один результат. Внутри своей ветви наблюдатель видит только один исход и теряет доступ к информации о других ветвях. Именно здесь возникает неполнота: наблюдатель не может доказать или проверить все истины, доступные Мультивёрсу целиком. Квантовые компьютеры могут исследовать всё пространство возможных решений в параллельных ветвях Мультивёрса. Но для наблюдателя это ничего не меняет, поскольку в результате декогеренции ему недоступна информация о фазовых корреляциях с параллельными ветвями ВФ.

Мультивёрс в целом (универсальная волновая функция) рассматривается как полная и непротиворечивая структура, охватывающая все возможные вычисления и истины. Мы можем постулировать существование универсальной волновой функции как полного описания мультивёрса, но не можем её вычислить или исчерпывающе описать алгоритмически. В этом смысле она напоминает «гёделевскую истину»: мы знаем, что она должна существовать в рамках квантовой теории, но внутри наших формальных систем не можем вывести её полностью. В каждой отдельной ветви мы не можем доказать все истины о Мультивёрсе, точно узнать меру других ветвей и вычислить полную волновую функцию наблюдаемой Вселенной, поэтому теоремы Гёделя и Тьюринга остаются в силе. В частности, остаётся проблема меры и выведения правила Борна: как именно выбрать статистический вес ветвей? Множество декогерентных историй, квазиклассических миров или систем отсчёта невозможно объединить в одну полную и непротиворечивую классическую реальность. Система будет или неполной, или противоречивой, или где-то в суперпозиции между полнотой и непротиворечивостью.

Квантовая механика обладает фундаментальными симметриями (унитарность, сохранение вероятности, симметрии физических законов). Эти законы симметрии одинаковы во всех ветвях универсальной волновой функции. Как я рассказывал в статье «Правда и мифы о Мультивёрсе», Мультивёрс Эверетта лучше всего визуализировать в 3D как фрактальное дерево или одуванчик с бесконечно ветвящимися «зонтиками». Теперь вспомните математическое дерево из начала данной статьи. Оба дерева фрактальны: простая рекурсивная формула порождает бесконечно сложную структуру. Уравнение Шрёдингера задаёт рекурсивную динамику: состояние системы в один момент времени однозначно определяет её состояние в другой момент. На уровне универсальной волновой функции эволюция полностью детерминистична: нет случайности, есть только разветвление. Случайность возникает лишь для наблюдателя внутри ветви, который видит один исход. Волновая функция всего Мультивёрса алгоритмически проста – она задаётся компактным уравнением Шрёдингера, подобно тому, как множество Мандельброта задаётся короткой рекурсивной формулой. Но её отдельные ветви, которые мы воспринимаем как квазиклассические миры, обладают огромной и неприводимой сложностью. Так же и для вычисления каждого отдельноого элемента множества Мандельброта требуется множество вычислительных итераций. Это значит, что сложность является субаддитивной величиной: части сложнее целого, простая глобальная формула порождает локально чрезвычайно сложные структуры.

Здесь мы сталкиваемся с очередным парадоксом. Универсальная волновая функция, охватывающая все возможные состояния вселенной, фактически содержит ответы на все неразрешимые математические задачи. Мы не можем её алгоритмически построить: она выходит за пределы тьюринговой вычислимости. Однако в каких-то её ветвях обязательно будут присутствовать все невычислимые величины, и даже строки символов, похожие на алгоритмы их вычисления или доказательства недоказуемых утверждений. Конечно, эти алгоритмы будут ошибочными, хотя в Мультивёрсе можно найти как доказательства их ложности, так и доказательства их истинности, а также доказательства ложности этих доказательств, и т.д. Разумеется, настоящее доказательство должно быть выведено по правилам системы, а не получено случайно. Даже если где-то существует правильный ответ на неразрешимый вопрос, его никак не получится проверить. Но как быть, если наблюдатель в какой-то маловероятной ветви Мультивёрса узнает точное значение константы Хайтина? Ведь это означало бы, что он станет всезнающим оракулом, способным решить задачу остановки для любой программы и решить любую неразрешимую задачу? Разве теоремы Гёделя и Тьюринга не запрещают существование таких оракулов во всех ветвях? Или они работают не во всех ветвях? Неужели в отдельных мирах гипервычисления всё-таки возможны?

Нет, Омега невычислима никаким алгоритмом, а случайное её получение не считается гипервычислением. Не существует физически возможного процесса, который за одно обращение даст на выходе всё бесконечное число знаков после запятой константы Хайтина. В лучшем случае наблюдатель может побитово получать Омегу с помощью квантового генератора случайных чисел, но он будет делать это не быстрее, чем решать задачу остановки запуском программы. Кроме того, у наблюдателя нет иной возможности проверить, правильное ли значение Омеги он получил, кроме как запустить все возможные программы на соответствующем языке. Даже если наблюдатель каким‑то образом узнает точное значение константы Хайтина (Ω), он получит оракул к задаче остановки и множеству других неразрешимых задач, но это не делает его абсолютно всезнающим демоном Лапласа: остаётся несчётное множество ещё более сложных невычислимых объектов и неразрешимых задач, решение которых закодировано числом Супер‑Ω. Таким образом, пределы Гёделя и Тьюринга не исчезают, а лишь смещаются на новый уровень: остаются более высокие уровни невычислимости, которые невозможно охватить.

С перспективы Мультивёрса квантовое вычисление выглядит как интерференция ветвей волновой функции. Случайный процесс – это когда все возможные исходы равновероятны, т.е. после измерения в каждой ветви будет получен свой результат. Но если имеется квантовый алгоритм решения задачи, он повышает вероятность правильных ответов и снижает вероятность неправильных. Иначе говоря, конструктивная интерференция усиливает амплитуды правильных исходов измерения, а деструктивная интерференция подавляет амплитуды неправильных исходов. В итоге в большинстве вселенных при измерении будет получен правильный ответ. В пределе мы получаем классический алгоритм, когда во всех вселенных одни и те же данные на входе приводят к одним и тем же данным на выходе. То есть по сути алгоритм – это физический объект, изменяющий «веса» ветвей волновой функции и определяющий меру распределения миров на выходе. Любой ответ можно получить случайно, неалгоритмическим путём. Но это не даст никаких вычислительных преимуществ, поскольку невозможно будет даже проверить его правильность. Исключение составляют только NP-задачи, ответы на которые можно проверить на классическом компьютере за полиномиальное время. Но как минимум некоторые из них (а может быть и все) эффективно разрешимы на квантовом компьютере за то же полиномиальное время.

Так если рассматривать мультивселенную Эверетта как единый квантовый компьютер, который вычисляет все свои возможные физические состояния, он будет полной, самодостаточной и непротиворечивой системой? Нет, в интерпретации Эверетта универсальная волновая функция эволюционирует детерминированно и алгоритмично по уравнению Шрёдингера, следовательно, на неё распространяются теоремы Гёделя. Тот факт, что все возможные исходы квантовых процессов реализуются в параллельных ветвях, не делает систему противоречивой, поскольку события в каждой отдельной ветви самосогласованы, а сами ветви ортогональны в гильбертовом пространстве. Даже если внутри отдельной вселенной всё остаётся алгоритмически описуемым, сохраняется неполнота: существуют истины о мультивселенной, которые не могут быть доказаны внутри её формальной теории. Полное моделирование Мультивёрса является неприводимой, но алгоритмической задачей. Параллельные миры Эверетта и космологические миры с другими константами можно описать алгоритмически только как единое целое, но смоделировать и предсказать эволюцию каждой отдельной вселенной мы не способны. Что же является аналогом недоказуемых гёделевских утверждений для всего Мультивёрса?

Как мы выяснили в статье «Модальный реализм Дэвида Льюиса», пространство всех логически возможных миров гораздо шире, чем пространство физических миров мультивселенной. Например, возможны миры с другими законами физики, другими логиками или неалгоритмическими процессами.  Можно достичь полноты и непротиворечивости формальной системы ценой неполноты метасистемы. Если алгоритмическая теория всего не может полностью описать вселенную, мы расширяет её до метатеории всего, которая даст полное описание вселенной, но не сможет до конца описать мультивселенную. Мультивселенная с разными законами физики – это не полная и противоречивая система, а скорее неполная, но непротиворечивая метасистема, которая объединяет множество отдельных формальных систем. Она непротиворечива, потому что каждый мир со своими законами замкнут и непротиворечив внутри себя. Но как целое она остаётся неполной: всегда будут истины о множестве миров, которые нельзя доказать внутри одной общей теории. Например, «существует мир с такими‑то свойствами» может быть истинным, но недоказуемым в рамках метатеории. Нет ни одной вселенной, в которой одновременно действуют разные законы физики – это нарушало бы принцип интероперабельности информации, который мы разбирали в предыдущей статье.

Каждая формальная система допускает бесконечное множество логически возможных миров. Это множество включает физически невозможные миры, невычислимые никаким алгоритмом. В статье «Мозг и мультимодальные нейросети как генераторы виртуальной реальности» я рассказывал о логически возможных средах Кантгоуту, которые нельзя передать в виртуальной реальности и смоделировать алгоритмом. Дэвид Дойч доказал их существование тем же диагональным методом, который использовали Кантор, Гёдель и Тьюринг (CantGoTu). Это логически возможные миры с другой физикой, допускающей гипервычисления и решающей неразрешимые математические проблемы. Таких невычислимых миров несчётное бесконечное множество, тогда как вычислимых миров – счётная бесконечность. В мирах Кантгоуту возможны гиперкомпьютеры с иным репертуаром вычислимых задач, то это фактически означает, что там будут действовать другие основания математики и логики. Но речь идёт не о том, что они нелогичны и парадоксальны, а о том, что границы вычислимого и доказуемого будут иными, чем в нашей Вселенной.

В таких мирах часть гёделевских истин становится конструктивно доказуемой; границы «вычислимого» и «доказуемого» сдвигаются. Базовые законы (непротиворечивость, закон исключённого третьего) могут сохраняться, но изменится то, что считается вычислимым и доказуемым. Это приведёт к новым классам теорем, которые там будут конструктивно доказуемы, а у нас останутся лишь аксиоматически постулируемыми или вовсе недостижимыми. Отсюда следует, что вычислимость – это не универсальное свойство всех возможных миров, а ограничение именно нашей физической реальности. Но в гипервычислительных мирах всё равно останутся неразрешимые задачи и недоказуемые утверждения. Например, там будет разрешимой задача остановки для машины Тьюринга, но неразрешимой задача остановки для самого гиперкомпьютера. Существуют гипотетические сверхквантовые модели, в которых корреляции результатов измерений Алисы и Боба сильнее, чем в квантовой механике, но не позволяют передавать информацию быстрее скорости света. В квантовой механике нарушения неравенств Белла ограничены пределом Цирельсона: 2√2 = 2.828… Но в принципе релятивистская причинность (отсутствие сверхсветовой коммуникации) допускает ещё более сильные корреляции: вплоть до 2√4 = 4.

Пример устройства, обеспечивающего максимально возможные корреляции – это коробки Попеску-Рорлиха (PR-box), предложенные Санду Попеску и Даниэлем Рорлихом в 1994 г. Они не дают прямого решения проблемы остановки, но нарушают известные ограничения на коммуникационную сложность и фактически делают возможным решение задач, которые в обычной модели требуют экспоненциальных ресурсов. Например, PR-box позволяет двум сторонам мгновенно вычислять скалярное произведение двух битовых строк, обмениваясь всего одним битом информации. В классической и квантовой модели вычисление скалярного произведения двух nn-битовых строк требует передачи порядка nn бит информации. С PR-box достаточно одного бита, т.е. информации передано меньше, чем реально получено. Если такие устройства доступны, то многие задачи из класса NP можно решать с экспоненциальным ускорением. В частности, PR-box позволяет свести проверку решений к тривиальным коммуникационным протоколам. Есть результаты, показывающие, что доступ к сверхквантовым корреляциям может фактически уравнять классы P, NP и PSPACE, делая их вычислительно эквивалентными. То есть задачи, которые обычно требуют экспоненциальной памяти и времени, становятся решаемыми за полиномиальные ресурсы. В стандартной теории сложности P ≠ NP (по крайней мере, так предполагается), и уж точно P ≠ PSPACE. Но даже если бы скорость света была другой или постоянная Планка имела иное значение, сама логика квантовой вероятности и линейной суперпозиции не изменилась бы настолько, чтобы допустить PR-box. Чтобы PR-box был возможен, нужно изменить саму структуру физических законов, а не их параметры. Это означало бы отказ от квантовой механики как теории с гильбертовым пространством и переход к более общей сверхквантовой теории.

Если вам кажется, что я зашёл слишком далеко, и вообще пора уже завязывать, то так оно и есть. Но я пойду ещё дальше и выскажу собственную безумную гипотезу, как снять проблему выбора между неполнотой и неалгоритмичностью теории всего, а также примирить многомировые метатеории с теориями квантово-гравитационных скрытых параметров. Это не чисто моя выдумка, подобные идеи уже предлагали в своих космологических интерпретациях Энтони Агирре, Макс Тегмарк и Леонард Сасскинд, о чём я рассказывал в статье «Иерархия мультивселенных». Так вот, не может ли оказаться, что те самые невычислимые миры, которые мы помещаем за пределы наблюдаемой алгоритмической Вселенной, каким-то отразом проецируются на сферу Хаббла и проявляются в нашем мире в виде невычислимых квантово-гравитационных степеней свободы?

Здесь нам пригодится принцип дополнительности горизонтов, который является обобщением принципа комплементарности чёрных дыр Леонарда Сасскинда, в свою очередь связанного с квантово-механическим принципом дополнительности Нильса Бора. Напомню, что принцип дополнительности Бора говорит о том, что для полного описания квантовой системы нам нужно применить два взаимоисключающих классических описания – например, классические описания электрона как волны и как частицы совмещаются в корпускулярно-волновом дуализме квантовой механики. Аналогично мы можем описать чёрную дыру изнутри с точки зрения падающего на сингулярность наблюдателя или снаружи с точки зрения наблюдателя на орбите, измеряющего излучение Хокинга, а невозможность их встречи в будущем гарантирует отсутствие парадоксов. Дальнейшим развитием этой идеи стал голографический принцип: всё, что происходит внутри чёрной дыры, может быть закодировано на её горизонте событий или в гравитационном поле. Если же распространить этот принцип на всю наблюдаемую вселенную, которая напоминает вывернутую наизнанку чёрную дыру, то всё, что находится за нашим космологическим горизонтом, должно быть закодировано информацией на самом горизонте.

Наблюдаемая вселенная – это участок, который находится в причинно-следственной связи с наблюдателем, а остальная часть реальности состоит из возможных событий или миров. Тогда неалгоритмические части наблюдаемой вселенной, принципиально недоступные измерению, становятся доступными по крайней мере для неформального описания на языке параллельных вселенных. Космологический принцип дополнительности горизонтов позволяет рассуждать либо о том, что находится внутри наблюдаемой вселенной, либо о том, что снаружи её космологического горизонта. Но, согласно голографическому принципу, эта информация может быть дуальной: удалённые в бесконечном пространстве миры каким-то образом соответствуют скрытым степеням свободы в пределах нашей вселенной – вакуумным флуктуациям или квантово-гравитационным степеням свободы. Скажем, информацию об исчезнувших за горизонтом частях нашей вселенной может нести излучение Унру, возникающее в пустом пространстве де Ситтера с ускоряющимся горизонтом и аналогичное излучению Хокинга от чёрных дыр, инфляционные миры с другими константами могут оставлять отпечатки в виде флуктуаций реликтового излучения, реликтовых нейтрино и реликтовых гравитационных волн, а параллельные миры Эверетта проявляться в виде фазовых корреляций, определяя на первый взгляд случайные результаты квантовых измерений.

Вывод

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

• Неполнота Гёделя (математическая логика) – в любой достаточно мощной формальной системе существуют утверждения, которые истинны, но недоказуемы внутри системы, и сама эта система не может доказать свою непротиворечивость.

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

• Невычислимость Хайтина (теория информации) – для каждой формальной системы существует фиксированная константа Омега, ограничивающая способность системы доказать, что конкретная строка сложнее этой константы. Вероятность остановки произвольной программы случайна в том смысле, что её нельзя вычислить алгоритмом, который намного короче самого числа.

Удивительно, но открытие этих пределов не затормозило математику, а наоборот, способствовало развитию новых её разделов (теории вычислений и теории информации), и в конце концов привело к изобретению компьютеров, интернета, нейросетей и прочих технологий. Аналогично и открытые физических пределов вычислений способствует поиску новых объяснений. В любой интерпретации квантовой механики остаются нерекурсивные источники информации, которые нельзя использовать как вычислительный ресурс: в копенгагенской – истинная случайность результатов измерений, в многомировой – невычислимая мера ветвей волновой функции, в бомовской механике – нелокальные скрытые параметры, в супердетерминизме – неизвестные начальные условия, в теории гиперграфов Вольфрама – вычислительная неприводимость. От квантовой случайности нам никуда не деться, даже если она детерминирована на уровне Мультивёрса – ММИ не гарантирует, что мы можем узнать универсальную волновую функцию и предсказать результат любого измерения. В этом и заключается гёделевская неполнота наших теорий – всегда останутся непредсказуемые и невычислимые компоненты, будь то случайный коллапс волновой функции, интерференция с параллельными мирами или нелокальные скрытые параметры. Если бы вселенная была полностью вычислимой и рекурсивной, как фрактал, её можно было бы задать короткой формулой или правилом. Но она была бы симметричной, статичной и безжизненной. Именно наличие невычислимых аспектов делает её интересной и сложной.

Таким образом, из теорем Гёделя и физического принципа Чёрча-Тьюринга не следует, что физическая реальность абсолютно непознаваема, невычислима или парадоксальна. Если физическая Вселенная – замкнутая вычислительная система (машина Тьюринга), обязательно будут неразрешимые задачи, и мы как её часть не сможем доказать, что она логически непротиворечива, и что её физические законы не приведут к логическим абсурдам. Всегда будут истины, которые не выводимы из выбранной системы аксиом, и процессы, которые не поддаются алгоритмическому предсказанию. Недоказуемым и неопровержимым (независимым от системы) гёделевским утверждениям соответствуют физические процессы, результат которых определён, но не может быть вычислен изнутри системы. Например, хаотическая динамика (уравнения которой известны, но точное поведение невозможно вычислить с произвольной точностью), машины Busy Beaver (их поведение определено, но невозможно предсказать, остановятся они или нет), задача спектральной щели. И даже те физические процессы, которые в принципе вычислимы и могут быть описаны алгоритмически, часто оказываются непознаваемыми и недоступными на практике. Даже в рамках тьюринговой вычислимости остаются бесчисленные задачи, которые невозможно решить с конечными физическими ресурсами. Вычислимый процесс может быть настолько сложен, что разум или любая другая конечная машина не сможет его полностью просчитать за время существования Вселенной. Невозможность точного моделирования Вселенной уже достаточна, чтобы исключить абсолютное знание и гипотезу симуляции.

Теоремы Гёделя, Тьюринга и Хайтина не доказывают, что создать окончательную теорию всего невозможно. Они просто устанавливают границы формализации и алгоритмизации: любая формальная теория всего будет либо неполной (не охватывающей все истины), либо противоречивой (если попытаться охватить всё). Теорема Гёделя не запрещает всё более глубокого и точного понимания мира, она лишь ограничивает возможность формального завершения этого понимания. Мы можем асимптотически приближаться к истине, добавляя новые аксиомы, методы, эвристики, вероятностные оценки, опровергать ложное, доказывать частное, расширять систему. Даже если существуют невычислимые аспекты, это не значит, что мы не можем построить приближённые модели, достаточные для практического понимания, или описать систему на естественном языке. Для достижения полноты необходима метатеория – система, которая описывает другую систему снаружи. В физике это может быть мультивселенная, математическая структура вроде Рулиады Стивена Вольфрама или Конечный ансамбль Макса Тегмарка, в котором наша вселенная – лишь частный случай. На худой конец можно постулировать внешний по отношению к физической Вселенной сверхъестественный метафизический источник, будь то сверхтьюринговый симулятор, всезнающий Бог-оракул или Абсолютный Гиперхаос. Почему такое объяснение заведомо хуже, чем физическая или логическая мультивселенная, и как с помощью теорем Гёделя пытались доказывать или опровергать существование Бога, мы рассмотрим в отдельной статье.