«Computo, ergo sum. (Вычисляю – значит, существую.)» (Сет Ллойд)

«Существует удивительно тесная параллель между проблемами физика и криптографа. Система, в которой зашифровано сообщение, соответствует законам вселенной, перехваченные сообщения — имеющимся доказательствам, ключи на день или сообщение — важным константам, которые необходимо определить. Соответствие очень близкое, но предмет криптографии очень легко обрабатывается дискретной техникой, физика — не так легко.» (Алан Тьюринг)

«Всякая точная наука основывается на приблизительности» (Бертран Рассел)

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

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

Панкомпьютерализм против гипотезы симуляции

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

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

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

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

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

Цифровая физика или алгоритмическая теория всего

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

Парадигма цифрового мира появилась вместе с компьютерами в 40-х гг. XX века. Джон фон Нейман, разработчик первого универсального компьютера ENIAC, позаимствовал из статистической физики термин «энтропия» для вычисления меры квантовой запутанности, заложив основу квантовой теории информации, а затем посоветовал создателю классической теории информации Клоду Шеннону назвать энтропией меру неопределённости в сообщении. В 1957 г. физик Эдвин Джейнс написал статью «Теория информации и статистическая механика», в которой указал на фундаментальную связь физики и логических операций, лежащих в основе работы цифровых компьютеров. В 1961 г. Рольф Ландауэр открыл связь между энтропией и скоростью вычислений. Вскоре учёные обнаружили, что Вселенная похожа на компьютерную программу или сеть вычислительных процессов, которая преобразует информацию во времени по заданным правилам (законам физики). Термины «цифровая физика» и «цифровая философия» придумал в начале 70-х гг. Эдвард Фредкин – американский физик, компьютерный инженер и профессор MIT, изучавший обратимые вычисления и клеточные автоматы. Он предположил, что законы физики могут быть выражены на языке вычислительных операций, материя и энергия являются всего лишь информационными состояниями, а Вселенная может быть описана как компьютерная программа, работающая на некотором аппаратном устройстве.

В 1969 г. пионер информатики и создатель первого цифрового компьютера Конрад Цузе в книге «Вычислительное пространство» впервые рассмотрел Вселенную как гигантский цифровой компьютер или клеточный автомат. Клеточный автомат представляет собой решётку дискретных ячеек, каждая из которых может находиться в одном из конечного числа состояний и обновлять своё состояние дискретными шагами в зависимости от состояния соседних ячеек. На клеточных автоматах можно построить универсальный компьютер, игру «Жизнь» Джона Конвея и даже самовоспроизводящийся универсальный конструктор фон Неймана, несмотря на простоту исходных правил и ограничения двумерного пространства. Если же значения всех фундаментальных переменных нашей Вселенной и все переходы между её состояниями взаимно однозначно соотносятся с состояниями и переходами состояний клеточного автомата, возникает вопрос: чем физически являются эти клетки и как они взаимодействуют друг с другом, чтобы удовлетворять правилам своих клеточных автоматов? Очевидно, клетки автомата не являются элементарными частицами или другими известными физическими структурами, подчиняющимися четырём фундаментальным взаимодействиям. Поэтому их пытаются найти на планковских масштабах или считают программным обеспечением – чисто вычислительными абстрактными математическими сущностями. Сегодня традицию выводить физику из клеточных автоматов продолжают Стивен Вольфрам и Герард ‘т Хоофт.

В 1997 г. эксперт по ИИ Юрген Шмидхубер назвал Вселенную универсальной машиной Тьюринга, то есть компьютером, на котором можно реализовать любой возможный алгоритм обработки информации. В статье «Самый быстрый способ вычисления всех вселенных» он предположил, что существует очень короткая и быстрая программа, которая асимптотически оптимальным образом выводит все возможные программы и вычисляет все возможные вселенные со всеми типами физических констант и законов. Согласно Шмидхуберу, априорная скорость программы – это мера сложности, которая равна её размеру в битах плюс логарифму максимального времени, которое мы готовы потратить на её выполнение. Если процесс вычисления нашей вселенной оптимально использует ресурсы некоторой более высокоуровневой вселенной, он должен работать по принципу Speed Prior S, при котором кумулятивная априорная вероятность всех данных, вычисление которых с помощью оптимального алгоритма требует более O(n) ресурсов, равна 1/n. Это значит, что большинство данных, сгенерированных компьютером, вычислимы в течение нескольких микросекунд, некоторые занимают несколько секунд, немногие занимают часы, очень немногие занимают дни и т.д. Аналогично можно предсказать, что большинство событий во вселенной легко и быстро вычислимы, а трудновычислимые события достаточно редкие и маловероятные.

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

Всё из бита

В 1990 г. американский физик Джон Арчибальд Уилер в статье «Информация, физика, квант: поиск связей» предложил концепцию «it from bit» («всё из бита» или «вещество из информации»). Суть её сводится к тому, что все материальные объекты – вещество и излучение – могут быть проявлениями более фундаментальной сущности – информации. Ввиду того, что различные свойства элементарных частиц (масса, заряд, спин и т.д.) не имеют собственного смысла, а раскрываются лишь при взаимодействиях с другими частицами, Вселенную следует рассматривать как математическую структуру, вычисляющую саму себя на языке двоичного кода:

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

В качестве примера отсутствия у частиц объективных свойств до измерения обычно приводится эксперимент Уилера с отложенным выбором. В космической версии этого эксперимента двухщелевой перегородкой служит гравитационная линза – галактика, которую луч света от далёкого квазара огибает с разных сторон так, что мы видим одно изображение этого квазара справа от линзирующей галактики, а другое – слева. Если мы направим на каждое изображение по одному телескопу, а выходные лучи от телескопов – на детекторы, фотон должен заранее «выбрать», за миллиарды лет до прибытия на Землю, с какой стороны обойти галактику. Если же поместить перед детекторами подвижный светоделитель, превратив систему в космический интерферометр, фотон будет приходить в виде волны, огибая галактику со всех сторон. Но тогда получается, что выбор фотона – проявлять себя волной или частицей – зависит от решения астрономов ставить или не ставить светоделитель, принятого миллиарды лет спустя. Это означает одно из трёх: 1) решение астрономов передаётся фотонам назад во времени; 2) решение астрономов предопределено миллиарды лет назад, когда фотон «выбрал» свой путь; 3) фотон нигде не локализован до момента его измерения или следует всеми путями одновременно. Уилер выбрал третий вариант, но вместо многомировой интерпретации, предложенной его учеником Хью Эвереттом, разработал теорию «всё из бита».

Ранее, в 1983 г. Джон Уилер сформулировал свой Антропный принцип участия (АПУ):

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

Уилер сравнивал принцип участия с игрой «двадцать вопросов», участник которой должен угадать задуманное слово, задавая вопросы и получая на них ответы «да» или «нет». Каждый следующий ответ логически совместим со всеми предыдущими и сужает область поисков, пока спрашивающий не остановится на определённом слове. Но никакого загаданного слова может и не быть – игрок сам создаёт его, задавая вопросы. Аналогично и наш разум, согласно Уилеру, может играть некоторую роль в создании вселенной. Учёный проиллюстрировал это U-образной петлёй обратной связи, на одном конце которой – момент Большого взрыва, а на другом – глаз наблюдателя, повёрнутый к этой точке:

«Вселенная представляет собой странную петлю, в которой физика порождает наблюдателей, а наблюдатели порождают физику… По существу, Вселенная – это обрабатывающая информацию система, в которой на более высоких уровнях возникает понятие материи».

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

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

Или, как говорил Нильс Бор, ни одно элементарное квантовое явление не является явлением, пока «оно не было доведено до конца необратимым актом усиления». Наблюдение квантовой системы – один из таких актов усиления, которые могут происходить и без участия наблюдателя. Учитывая, что наши решения, когда и в каком базисе измерять частицу, тоже могут зависеть от квантовых событий, мы являемся сотворцами реальности в той же степени, что и поляризаторы света или магниты Штерна-Герлаха. Любое взаимодействие частиц можно рассматривать как элементарный акт вычисления, вопрос и ответ. Но означает ли это, что сама реальность сводится к битам? Нет, это означает лишь то, что научное описание реальности сводится к битам. Снова процитируем Бора: «Неправильно думать, что задача физики — выяснить, какова Природа. Физика касается того, что мы можем сказать о Природе».

Сам Уилер, оценивая энтропию реликтового излучения наблюдаемой вселенной числом 8*10⁸⁸, отмечает, что рассматривать её как меру незнания наблюдателем всей информации о системе и структурировать вселенную битами просто нелепо:

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

Но с чем тогда можно соотнести эти биты, если они не существуют объективно до измерения и физически не помещаются в голове наблюдателя? По версии Уилера, «строительным элементом [вселенной] является элементарное квантовое явление «да, нет». Это абстрактная сущность. Она не локализована в пространстве и времени». То есть Вселенная состоит из чистой информации. Как же могут конкретные физические явления быть реализациями абстрактной математической сущности? Очевидно, идея «всё из бита» восходит к пифагорейской формуле «всё есть число» и сталкивается с той же проблемой, с которой столкнулся Пифагор – иррациональными числами вроде √2, которому равна диагональ квадрата со стороной 1. Их попросту невозможно вычислить и записать в цифровых битах, то есть потребуется задать бесконечно много вопросов с ответами «да» или «нет», чтобы получить одно такое число.

«Некоторые люди полагают, будто Уилер в последние годы жизни спятил. Но на самом деле он всегда был чокнутым» - так Ричард Фейнман отзывался о своём научном руководителе. Иронично, что Уилер пережил Фейнмана на 20 лет и сохранил ясность ума до глубокой старости. Так может, Уилер всё-таки был прав?

Вселенная – универсальная машина Тьюринга?

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

1. «и» – два входных бита преобразуются в один выходной, который равен 1 в том и только в том случае, если оба входных бита равны 1, в остальных случаях на выходе появится 0;

2. «или» – два входных бита переходят в один выходной, который равен 1, если хотя бы один входной бит равен 1, если же оба входных бита равны 0, то и выходной будет равен 0;

3. «не» – операция, инвертирующая входной бит, то есть превращающая 0 в 1, а 1 в 0;

4. «копировать» – входной бит 0 превращается в два выходных бита 00, входной бит 1 – в два выходных 11.

Из этих логических элементов (вентилей) можно составить логические схемы, а из логических схем – алгоритмы.

Алгоритмы работы нашей Вселенной – её исходный код – это законы физики. Если абстрагироваться от «словесного багажа», любой закон физики – это некая формула. Формула выражает соотношение измеряемых величин, которые могут быть постоянными (константами) или переменными. Правило, определяющее изменение какой-либо переменной величины (например, энергии) по отношению к постоянной (например, скорость света), является простейшим алгоритмом. Известные нам формулы и константы – это не более чем приближённые теоретические модели, основанные на доступных сегодня фактических данных. Как и в программировании, одно и то же явление можно закодировать разными способами. Например, открытое Хуаном Малдасеной AdS/CTF-соответствие говорит о том, что теория гравитации в пятимерном анти-деситтеровском пространстве эквивалентна конформной теории поля в четырёхмерном пространстве без гравитации. Иначе говоря, есть два совершенно разных исходника для одной и той же программы. А учёные в чём-то напоминают программистов, которые занимаются реверс-инжинирингом (обратной разработкой): и те, и другие пытаются по данному им образцу воссоздать исходный код программы или написать аналогичную программу с другим кодом.

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

Критики физикализма говорят, что современные физические теории не могут объяснить и тем более предсказать такие явления, как сознание и свободная воля. Например, Роджер Пенроуз утверждает, что сознание неалгоритмично и имеет квантовую природу. Его совместную со Стюартом Хамероффом гипотезу я уже подвергал сомнению в статье «Квантовое сознание». Даже если квантовые эффекты играют какую-то роль в работе мозга, наиболее вероятно, что они являются источником случайности. Но это не исключает вычислительной модели сознания, просто в его основе будут лежать недетерминированные квантовые алгоритмы. А значит, ничто не мешает смоделировать сознание по крайней мере на квантовом компьютере. Вот что пишет Сет Ллойд в книге «Программируя Вселенную»:

«Будучи людьми, мы всего лишь подсистемы Вселенной, сложность которых оценивается примерно в 10³⁰ битов. Это может быть технически невозможно, но, похоже, нет теоретических возражений против идеи, что мы в принципе можем создать точную копию человеческого существа, либо в виде прямой физической копии, либо в виде компьютерной симуляции. Такой «искусственный» человек будет испытывать осмысленный мир, но этот опыт будет эмерджентным».

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

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

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

Универсальная машина Тьюринга может считывать описание других машин Тьюринга (алгоритмы и входные данные), моделировать их на своей собственной входной ленте и выдавать на выходе тот же результат, что и симулированная машина. Система, которая может имитировать универсальную машину Тьюринга, называется полной по Тьюрингу. Современные цифровые компьютеры считаются универсальными: они могут выполнять любую выполнимую программу и вычислять любую алгоритмически вычислимую функцию натуральных чисел, без учёта ограничений по времени и памяти.

На самом деле по-настоящему универсальных классических компьютеров не существует, хотя бы потому, что ни один компьютер не может работать вечно и не обладает бесконечной памятью. Большинство типов классических компьютеров, начиная с аналитической машины Бэббиджа и заканчивая современными суперкомпьютерами на кремниевых видеокартах, требуют очень точной настройки, подгонки деталей, специальных материалов и т.д. По той же причине нереалистичны идеализированные модели вроде компьютера на бильярдных шарах, предложенного Фредкином и Тоффоли в 1982 г. – они нестабильны из-за хаоса, малейшее отклонение в начальных условиях будет приводить к ошибкам. К счастью, квантовые компьютеры лишены этого недостатка, потому что в квантовой механике нет чувствительности к начальным условиям – эффекта бабочки.

Как я объяснял в одной из своих публикаций, квантовый компьютер – аналоговая, а не цифровая машина. Квантовые вычисления — это манипуляция кубитами в соответствии с законами квантовой механики. Кубит – квантовая система, которая имеет континуум доступных физических состояний, но при измерении может принимать только одно из двух базисных состояний. В отличие от классических битов, кубиты могут находиться в суперпозиции базисных состояний 0 и 1 в разной степени, и квантово запутываться друг с другом в процессе вычисления. Квантовые вычисления имеют вероятностную природу и не сводятся к ответам «да/нет». Кроме того, в некоторых случаях можно получить ответ, задавая наводящие вопросы или вообще не задавая вопроса. Это разные виды слабых и бесконтактных измерений, а также контрфактические вычисления, о которых я писал в отдельной статье.

Если не брать в расчёт технические сложности масштабирования числа кубитов, квантовый компьютер может эффективно моделировать классическое вычисление, но классический компьютер не может эффективно моделировать квантовое вычисление. Классический бит легко кодируется одним физическим кубитом, но кубит нельзя закодировать с помощью одного классического транзистора. Для кодирования n-кубитной квантовой системы требуется 2ⁿ комплексных чисел. Например, для моделирования 300-кубитного квантового компьютера необходимо записать в битах 2³⁰⁰ комплексных чисел – больше, чем частиц во Вселенной. Для моделирования волновой функции также потребуются огромные (почти бесконечные) вычислительные мощности. Об этом говорил ещё в начале 80-х гг. Ричард Фейнман:

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

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

«Квантовое моделирование — это процесс, в котором квантовый компьютер имитирует другую квантовую систему. Из-за различных типов квантовой странности классические компьютеры могут имитировать квантовые системы только неуклюжим, неэффективным способом. Но поскольку квантовый компьютер сам по себе является квантовой системой, способной демонстрировать полный репертуар квантовой странности, он может эффективно имитировать другие квантовые системы. Полученное моделирование может быть настолько точным, что поведение компьютера будет неотличимо от поведения самой моделируемой системы» (Сет Ллойд)

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

Невычислимость и проблема остановки

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

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

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

Разумеется, квантовый компьютер не является волшебной палочкой, решающей любую невычислимую задачу. Доказано, что квантовый компьютер PSPACE-приводим, т.е. квантовый компьютер, работающий полиномиальное время, может быть смоделирован на классическом компьютере, использующем полиномиальное пространство. Другими словами, работу квантового компьютера можно смоделировать на классическом с конечной памятью при наличии бесконечного времени. Для квантового компьютера остаются неразрешимыми задача остановки, многие задачи класса EXPTIME (решаемые детерминированной машиной Тьюринга за экспоненциальное время) и все задачи класса EXPSPACE (требующие экспоненциально большого количества памяти).

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

Тезис Чёрча-Тьюринга-Дойча

В 1985 г. Дэвид Дойч и Стивен Вольфрам независимо друг от друга сформулировали «сильный», или физический тезис Чёрча-Тьюринга, также называемый тезисом Чёрча-Тьюринга-Дойча (CTD) или тезисом Дойча-Вольфрама. По версии Дойча, «Каждая конечная доступная пониманию физическая система может быть полностью симулирована с помощью универсальной машины для вычисления моделей, действующей конечными методами». По версии Вольфрама, «Универсальные компьютеры настолько же мощны в своих вычислительных возможностях, насколько может быть любая физически реализуемая система, так что они могут моделировать любую физическую систему».

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

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

Всё из кубита

Гипотеза «всё из кубита» (It from Qbit) берёт начало в одноимённой статье Дэвида Дойча 2002 г. и в статье Сета Ллойда «Вселенная как квантовый компьютер» 1999 г. В отличие от цифровой физики, которая претендует на статус «теории всего», заменяющей квантовую механику, «всё из кубита» - не более чем переформулировка квантовой механики на языке квантовых вычислений, без изменений в её математическом аппарате и предсказаниях. Её сторонники утверждают, что фундаментальной реальностью является универсальная волновая функция, а классические биты и вычисления с ними – это аппроксимация. Мир не может быть результатом классических вычислений, потому что с их помощью невозможно эффективно моделировать квантовые явления. Никто не знает, как вывести природу физического мира из бита, и это вряд ли когда-нибудь будет возможно. Даже если теория со скрытыми параметрами воспроизведёт все предсказания квантовой механики, она не даст никаких дополнительных предсказаний, проверяемых на практике – это будет очередная «теория чего угодно», предлагающая 100500 различных рекурсивных функций, но не указывающая, какая же из них описывает именно нашу Вселенную. Мы никогда не сможем с точностью предсказать будущее состояние системы по её текущему состоянию – это невычислимая по Тьюрингу задача.

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

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

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

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

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

Голографический принцип ограничивает количество классической информации в битах четвертью от числа планковских ячеек на границе. Это значит, что полное пространство состояний любой пространственно конечной квантовой системы тоже конечно, т.е. она может содержать только конечное число кубитов. Но голографический принцип не накладывает ограничений на количество возможных состояний одного кубита. Кубит может находиться в одном из бесконечного числа чистых или смешанных состояний, отображаемых стрелками внутри сферы Блоха. В каждый момент времени каждый из конечного числа кубитов находится в определённом состоянии, соответственно количество информации в системе конечно и не превышает предел Бекенштейна. Отсюда следует, что невозможна машина Тьюринга с конечными пространственными размерами и бесконечной памятью.

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

Невычислимость результата квантового измерения следует из принципа неопределённости Гейзенберга, который позволяет узнать только координату или импульс частицы, или измерить спин электрона только по одной оси. Физически невозможно получить проекцию спина сразу на две или три оси: как только мы измеряем его направление («вверх» или «вниз») по одной оси, направление по ортогональным осям («вправо» и «влево») или («вперёд» и «назад») становится максимально неопределённым и при следующем измерении принимает случайное значение с вероятностью 50/50. Аналогично дело обстоит с поляризацией фотона: измерив её по диагонали, вы получаете равновероятную суперпозицию вертикальной и горизонтальной поляризаций, а измерив по вертикали или горизонтали – получаете суперпозицию +45° и -45°. С точки зрения многомировой интерпретации это значит, что любое измерение кубита расщепляет Вселенную на множество миров со всеми возможными значениями спина по всем возможным осям – невозможно приготовить кубит в таком состоянии, чтобы при измерении в любом базисе он всегда давал один и тот же ответ – «да» или «нет». Вот что пишет об этом Дэвид Дойч в статье «Всё из кубита»:

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

То, что мы воспринимаем в некоторой степени приближения как мир однозначных переменных, на самом деле является частью большей реальности, в которой полный ответ на вопрос «да-нет» никогда не бывает просто «да» или «нет», и даже не «да» и «нет» одновременно, а квантовой наблюдаемой –– чем-то, что можно представить как большую эрмитову матрицу. Действительно ли возможно представить мир, включая нас самих, как «состоящий из матриц» в этом смысле? Зенон фактически задавал тот же вопрос о действительных числах в классической физике: как мы можем состоять из действительных чисел? Чтобы ответить на этот вопрос, мы должны поступить так, как сделал Зенон, и проанализировать поток информации – обработку информации – которая бы происходила, если бы эта концепция реальности была верной. Можем ли мы быть «состоящими из матриц», сводится к следующему: какой опыт будет у наблюдателя, полностью состоящего из матриц, живущего в мире матриц? Теории декогеренции и последовательных историй ответили на этот вопрос довольно подробно: на грубозернистом уровне мир выглядит так, как будто классическая физика верна; и как будто классические теории информации и вычислений также верны. Но там, где происходят когерентные квантовые процессы - в частности, квантовые вычисления - такой видимости нет, и в игру вступает экспоненциально более богатая структура».

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

Вывод

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