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

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

«Если вы ничего не знаете о компьютерах, просто помните, что это машины, которые делают ровно то, что вы им говорите, но часто удивляют вас результатами» (Ричард Докинз)

«Информатика — эмпирическая дисциплина. [...] Каждая новая созданная машина — это эксперимент. Само создание машины — это вопрос к природе; и мы прислушиваемся к ответу, наблюдая за работой машины и анализируя её всеми доступными аналитическими и измерительными средствами. Каждая новая созданная программа — это эксперимент. Она бросает вопрос природе, а её поведение даёт ключи к ответу» (Аллен Ньюэлл)

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

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

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

Философский агностицизм и скептицизм

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

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

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

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

Девиз всех агностиков – Ignoramus et ignorabimus (лат. «не знаем и не узнаем») – крылатое выражение из доклада Эмиля Дюбуа-Реймона «О пределах познания природы», на которое Давид Гильберт ответил не менее знаменитым «Мы должны знать – мы будем знать!». Этот спор между гносеологическими пессимистами и оптимистами продолжается по сей день, несмотря на то, что сам процесс познания перестал быть привилегией человеческого разума. Эволюционная эпистемология показала, что производство знания путём вариации и отбора – универсальный механизм, присущий природе изначально и действовавший задолго до появления нашего вида. Но если создавать знание могут искусственный интеллект, квантовый компьютер, живые организмы и даже примитивные молекулы-репликаторы, должен существовать и универсальный предел познания, ограничивающий возможности не только человеческого разума, но и других вычислительных систем. Такой предел был открыт в 1930-е гг. Куртом Гёделем, Алонсо Чёрчем и Аланом Тьюрингом.

Вычислительная и физическая универсальность

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

Считается, что универсальными, или тьюринг-полными, являются системы, на которых можно запустить Doom. Вся магия универсальности состоит в том, что нам не нужно изменять конструкцию машины для каждой отдельной задачи – достаточно запрограммировать её, и она выполнит любое вычисление. Всё, что в принципе вычислимо, может быть смоделировано машиной Тьюринга. Есть менее мощные вычислительные модели вроде конечного автомата, которые не являются тьюринг-полными. Известно, что магазинные автоматы (PDA) мощнее детерминированных (DFA) и недетерминированных (NFA) конечных автоматов. Но при проектировании вычислительных машин быстро достигается точка универсальности, когда добавление дополнительного оборудования не изменяет набор вычислимых функций машины. Здесь необходимо пояснение. В теории алгоритмов класс выполнимых компьютером задач называется вычислительной мощностью, но в обиходе это словосочетание чаще ассоциируется с производительностью компьютера, измеряемой в флопсах. Во избежание путаницы мы будем называть мощность машины Тьюринга её репертуаром. Репертуар универсальной машины Тьюринга ограничен вычислениями с рациональными числами, которые составляют ничтожную долю от всех действительных чисел. Только такие вычисления можно описать пошаговым алгоритмом, а большинство действительных чисел не имеют конечного описания.

В 1936 г. Алонзо Чёрч и Алан Тьюринг сформулировали классический тезис Чёрча-Тьюринга, согласно которому любая функция, которую мы интуитивно считаем вычислимой, может быть вычислена машиной Тьюринга. Под «интуитивно вычислимой» они подразумевали функцию, которую математик может вычислить с помощью ручки и бумаги, используя конечный набор простых алгоритмов. И наоборот, функция над натуральными числами может быть вычислена человеком, следующим алгоритму, тогда и только тогда, когда она вычислима машиной Тьюринга. Тезис Чёрча-Тьюринга установил эквивалентность математика и компьютера, а также других вычислительных машин. Все тьюринг-полные формальные модели вычислений (λ-исчисление Алонзо Чёрча, машина Тьюринга, рекурсивные функции Стивена Клини и т.д.) эквивалентны по мощности, т.е. имеют одинаковый репертуар вычислимых функций. Простейшими такими системами с доказанной тьюринг-полнотой являются клеточные автоматы: Правило 110 и игра «Жизнь» Джона Конвея. Другие примеры – «разностная машина» Чарльза Бэббиджа, механическая машина Тьюринга из LEGO, некоторые карточные игры, домино, машина Поста, алгоритм Маркова, сеть Петри и т.д. На первый взгляд между машиной Тьюринга, игрой «Жизнь», человеческим мозгом и новейшим суперкомпьютером мало общего. Действительно, эти устройства сильно различаются «железом», принципом работы, скоростью вычисления и объёмом памяти. Но с точки зрения репертуара они эквивалентны и не могут вычислять более эффективно, то есть выполнять больше математических функций, чем машина Тьюринга.

Первым, кто увидел в тезисе Чёрча-Тьюринга физический смысл, был биолог-теоретик Роберт Розен. Он переформулировал тезис как утверждение о невозможности определённого класса физических процессов и предположил, что ограничения в вычислениях объясняют факты о природе, однако на его работу никто не обратил внимания. В 1985 г. Дэвид Дойч в статье «Квантовая теория, принцип Чёрча-Тьюринга и универсальный квантовый компьютер» предложил считать тезис Чёрча-Тьюринга физическим принципом:

«Я предлагаю переосмыслить «функции Тьюринга, которые естественным образом считались бы вычислимыми» как функции, которые в принципе могут быть вычислены реальной физической системой. Ибо, конечно, было бы трудно считать функцию «естественно» вычислимой, если бы её нельзя было вычислить в Природе, и наоборот».

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

Важно отметить, что квантовый компьютер не расширяет множество алгоритмически вычислимых функций, а лишь ускоряет решение некоторых задач (например, факторизация, моделирование квантовых систем), которые решаются классическим компьютером крайне неэффективно. В теории сложности алгоритмов ключевым моментом в задаче является то, насколько быстро растёт время, необходимое для её решения, по мере увеличения размера задачи. Время измеряется количеством элементарных шагов, необходимых алгоритму для нахождения решения. Различают P-задачи, решаемые машиной Тьюринга за полиномиальное время, и NP-задачи («недетерминированное полиномиальное время»), которые не могут быть решены, но их решение может быть проверено за полиномиальное время. Эффективный классический алгоритм хотя бы для одной NP-полной задачи означал бы, что каждая NP-задача (включая все NP-полные) на самом деле является P-задачей. Никто до сих пор не доказал, P = NP или P ≠ NP, хотя большинство специалистов склоняются ко второй версии и выстраивают иерархию классов сложности так: P⊆BQP⊂NP⊂PSPACE. Здесь BQP – класс задач, решаемых квантовым компьютером за полиномиальное время, а PSPACE – задачи, требующие полиномиального увеличения памяти.

Класс BQP включает все P-задачи, а также несколько NP-задач, таких как факторизация и так называемая задача дискретного логарифмирования. Большинство других NP-задач выходит за рамки BQP, а это означает, что даже квантовому компьютеру потребуется более чем полиномиальное число шагов для их решения. Однако BQP может выходить за рамки NP, а это означает, что квантовые компьютеры могут решать некоторые задачи быстрее, чем классические компьютеры могут даже проверить ответ. Доказано, что универсальный квантовый компьютер PSPACE-приводим (квантовый компьютер, работающий за полиномиальное время, может быть смоделирован классическим компьютером, работающим в полиномиальном пространстве). С точки зрения вычислимости это значит, квантовая машина Тьюринга эквивалентна по мощности обычной машине Тьюринга. Обычная машина Тьюринга может имитировать квантовый компьютер, затрачивая экспоненциальное время. Неизвестно, превосходит ли квантовый компьютер по эффективности недетерминированную машину Тьюринга, которая может запускать экспоненциально много копий самой себя и тем самым решать за полиномиальное время NP-полные задачи, эффективное решение одной из которых обеспечит эффективное решение всех остальных.

Гипервычисления и суперрекурсивные алгоритмы

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

Чтобы доказать, что ваше устройство является гиперкомпьютером, нужно продемонстрировать что-нибудь из этого списка:

1. Решить одну из неразрешимых задач, для которых не существует алгоритма, дающего правильный результат для любого входного значения:
   - задачу остановки (определить, остановится ли произвольная программа, по её описанию и входным данным);
   - 10-ю проблему Гильберта (предложить алгоритм, который определяет, имеет ли произвольное диофантово уравнение целочисленные решения);
   - проблему соответствия Поста (дан набор пар строк; нужно определить, существует ли последовательность, при которой строки совпадут);
   - проблему доказуемости (создать алгоритм, который для любого утверждения в достаточно мощной формальной системе определит, доказуемо оно или нет);
   - проблему выводимости формулы в арифметике Пеано (правильно определить все истинные и все ложные утверждения формальной системы);
   - проблему усердного бобра (вычислить максимальное конечное число шагов машины Тьюринга с n состояниями);
   - проблему Гольдбаха (доказать утверждение о том, что любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел);
   - гипотезу Римана (доказать, что все нетривиальные нули дзета-функции Римана имеют действительную часть, равную 1/2);
   - гипотезу Коллатца (верно ли, что любая сиракузская последовательность чисел, строящаяся от произвольного натурального n, рано или поздно вырождается в единицу);
   - проблему умирающей матрицы (для данного конечного множества квадратных матриц n × n определить, существует ли произведение всех или некоторых из этих матриц в каком-либо порядке, дающее нулевую матрицу);
   - проблему простых чисел-близнецов (определить, конечно или бесконечно их количество);
   - проблему идеального сжатия данных (создание идеального архиватора, формирующего для любого входного файла программу наименьшего возможного размера, печатающую этот файл, или создание идеального оптимизирующего по размеру компилятора);
   - вычисление колмогоровской сложности произвольной строки;
   - другие задачи из класса невычислимых функций.

2. Решить одну из сверхзадач (supertasks), требующих выполнения счётно бесконечного числа вычислительных шагов за конечное время:
   - парадокс лампы Томсона (Лампу включают и выключают всё быстрее и быстрее: 1/2, 1/4, 1/8 секунды и т.д. Через 1 секунду совершено бесконечно много переключений. Вопрос: горит ли лампа в конце?);
   - измерения с бесконечной частотой (например, квантовый эффект Зенона);
   - проверка универсальных свойств программ («Выдаст ли программа когда-нибудь число 2025?»);
   - вычисление невычислимых действительных чисел (например, число Хайтина Ω -вероятность остановки случайной программы);
   - решение задач из теории игр с бесконечными ходами (доиграть бесконечную партию и определить победителя);
   - оперировать с бесконечно малыми и бесконечно большими величинами как с конечными объектами;
   - определить истинность или ложность неизвестных или даже неразрешимых утверждений арифметики Пеано методом прямого перебора всех натуральных чисел.

3. Решить одну из гиперзадач, требующих выполнить несчётное число операций за конечное время или оперировать с бесконечной точностью в физически реализуемых процессах:
   - определение принадлежности числа множеству (например, рационально ли число π?);
   - вычисление точного значения π или e (любая конечная аппроксимация неполна);
   - определение точного корня многочлена с иррациональным решением;
   - решение уравнений с хаотической динамикой (начальные условия требуют бесконечной точности);
   - определение траектории в задаче трёх тел (чувствительность к начальным условиям);
   - вычисление точного значения множества Мандельброта для произвольной точки;
   - определение точного значения интеграла с трансцендентным результатом;
   - решение уравнений с действительными коэффициентами, где результат зависит от бесконечной десятичной дроби;
   - определение точного положения частицы в квантовой механике (математически требует бесконечной точности);
   - вычисление точного значения хаотических аттракторов (например, логистическое отображение при r=4).

Если бы кто-то показал физическое устройство, которое систематически решает задачу остановки или сверхзадачу, это означало бы, что в природе реализуются процессы, которые не укладываются в рамки классической теории вычислимости, и что известные физические теории неполны или неверны в фундаментальном смысле. Но пока все наблюдения подтверждают, что физический мир ограничен тьюринговой вычислимостью. Большинство специалистов сходится во мнении, что сверхтьюринговые вычисления невозможны, и ставят гиперкомпьютер в один ряд с такими мифическими устройствами, как вечный двигатель и гипердрайв. Так, американский математик Мартин Дэвис категорически отрицал возможность гипервычислений и написал статью «Миф о гипервычислениях» (2004), в которой отметил, что все гипервычисления «сводятся лишь к очевидному замечанию о том, что если допускаются невычислимые входные данные, то достижимы и невычислимые выходные данные».

Прежде, чем перейти к теоретическим моделям гиперкомпьютеров, давайте разберёмся, какие машины гиперкомпьютерами НЕ являются:

1. Машина Тьюринга с более чем двумя символами в алфавите. Увеличение алфавита может сократить время работы машины Тьюринга, но не увеличивает вычислительную мощность (репертуар). Любой конечный алфавит можно однозначно сопоставить с двоичным кодом. Неважно, используете вы машинный код или высокоуровневый язык программирования – это не изменит класс вычислимых задач.

2. Машина Тьюринга с полубесконечной (бесконечной в одну сторону) лентой. Эквивалентна по репертуару обычной машине Тьюринга с бесконечной лентой. Это можно доказать биекцией между множеством целых чисел и множеством натуральных чисел.

3. Многоленточная машина Тьюринга. C машиной Тьюринга может быть связано более одной ленты, но это не увеличивает вычислительную мощность. Бывает и спаренная машина Тьюринга, у которой несколько лент и несколько головок чтения/записи. Каждая лента работает независимо, но все они управляются одной и той же программой. Параллельные вычисления и многоядерные процессоры ускоряют работу компьютера, но не расширяют его репертуар.

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

5. Вероятностная машина Тьюринга (PTM), случайная машина Тьюринга (RTM) или машина Тьюринга, подверженная ошибкам (FTM). Это разновидности детерминированной машины Тьюринга, имеющие дополнительный аппаратный источник случайных битов, любое число которых они могут «заказать», загрузить на отдельную ленту и потом использовать в вычислениях. Вероятностная машина на каждом шаге может делать случайный выбор между несколькими переходами с заданной вероятностью, случайная машина выбирает следующее состояние при каждом переходе с равной вероятностью, а подверженная ошибкам моделирует ненадёжное вычисление в условиях аппаратных сбоев и шумов. Однако ни истинная квантовая случайность, ни детерминированная псевдослучайность не делают невычислимые задачи вычислимыми. Генератор случайных чисел в качестве источника входных данных может создавать случайные невычислимые функции или помогать угадывать правильное решение, но не даёт гарантированных ответов на неразрешимые проблемы.

6. Аналоговый компьютер – машина, работающая не с дискретными символами, а с непрерывными физическими величинами (напряжение, ток, давление, скорость и т.д.). Хорошо подходит для решения дифференциальных уравнений и моделирования физических процессов, но не обладает встроенным механизмом универсальности: для новой задачи её нужно физически перенастраивать, поскольку «программа» обычно задаётся конфигурацией устройства (соединениями, параметрами), а не хранимым кодом. Идеализированный аналоговый компьютер Клода Шеннона может решать только алгебраические дифференциальные уравнения, в то время как цифровой компьютер может решать и некоторые трансцендентные уравнения. Существуют теоретические модели «универсальных аналоговых вычислений» (например, непрерывные вычислительные модели, системы дифференциальных уравнений, работающие как универсальные симуляторы), а некоторые непрерывные динамические системы могут имитировать машину Тьюринга. В идеализированных условиях (бесконечная точность измерений, отсутствие шума, непрерывное время) такие модели могут решать задачи, неразрешимые для машины Тьюринга. Но на практике аналоговые компьютеры не универсальны и не превосходят цифровые. Теоретически аналоговые компьютеры могли бы решать NP-полные задачи за полиномиальное время. Цифровым компьютерам необходимо кодировать всё в дискретные данные. Это приводит к экспоненциальному росту числа возможных решений. Например, для решения задачи коммивояжёра для 5 городов потребуется исследовать 5! = 120 маршрутов. Для n городов это будет n! маршрутов. Каждый маршрут необходимо закодировать в цифровом виде, что даёт n! различных вариантов. Однако аналоговый компьютер может кодировать все решения в едином непрерывном пространстве (технически многообразии), где каждая точка пространства представляет собой возможное решение. Такое пространство будет содержать решение в глобальном минимуме или максимуме. Мы могли бы использовать алгоритмы оптимизации, такие как градиентный спуск и имитация отжига, или какие-либо математические функции/операции для поиска этого минимума/максимума. Так же, как нам не нужно оценивать каждую отдельную точку для поиска максимумов и минимумов, эти методы не требуют исследования каждой отдельной точки многообразия, что позволяет избежать экспоненциального расширения, с которым столкнулись бы цифровые компьютеры. Однако аналоговые системы, основанные на физических явлениях, описываемых дифференциальными уравнениями, могут быть смоделированы обычными компьютерами за время, ненамного превышающее задержку таких систем. Таким образом, экспоненциальный выигрыш невозможен.

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

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

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

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

Модели гиперкомпьютеров

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

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

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

2. Машина Зенона, или ускоренная машина Тьюринга – выполняет первый шаг вычисления за 1 минуту, второй за ½ минуты, третий за ¼ и т.д., как в апории Зенона «Дихотомия». Время выполнения шага уменьшается вдвое после каждого шага, то есть получается бесконечная геометрическая прогрессия с отношением r = 1/2. Это значит, что она сходится, то есть стремится к определённому значению (2), а не бесконечно увеличивается. За конечное время (2 минуты) машина совершает счётно бесконечное число шагов. Мы просто передаём ей инструкцию вывести что-то в случае остановки и ничего в противном случае. Если мы получим вывод через 2 минуты, мы будем знать, что программа останавливается, в противном случае она будет работать вечно. Машины Зенона, по сути, являются машинами Тьюринга, способными выполнять сверхзадачи, то есть счётное бесконечное множество операций за конечное время. Классический аргумент Зенона можно сформулировать так. Движение – это сверхзадача, поскольку завершение движения на любое заданное расстояние требует бесконечного числа шагов. Сверхзадачи невозможны. Следовательно, движение невозможно. Машина Зенона – чисто математическая абстракция, физически невозможна (требует бесконечной энергии и точности). Согласно современным физическим теориям, время вырождается в море квантовых флуктуаций (квантовую пену) в масштабе порядка 10^–43 секунды (планковское время), что делает подобный тип машины невозможным.

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

3. Вечная (ITTM) или ординальная (OTM) машина Тьюринга – обобщения машины Зенона. Первая работает бесконечное время, но имеет конечные алгоритмы, состояния и ленты. Вторая имеет ленту произвольной ординальной длины. Вечная машина Тьюринга, предложенная в работе Джоэла Хэмкинса и Энди Льюиса «Машина Тьюринга с бесконечным временем», развивает идею ускоренного вычисления, позволяя машине выполнять ускоренное копирование машины Тьюринга. В крайнем случае это может быть бесконечное число запусков ускоренной машины Тьюринга. Благодаря этой способности бесконечная машина Тьюринга может решить больше задач, чем базовая ускоренная машина Тьюринга. Бесконечная машина Тьюринга может иметь бесконечное число состояний, но имеет конечное число переходов между состояниями. Легко увидеть, что конечная машина Тьюринга может определить любой язык, используя своего рода справочную таблицу. По той же причине бесконечная машина Тьюринга могла бы вычислить любую функцию над натуральным рядом чисел, включая проблему остановки. Трансфинитные вычисления позволяют машине работать в течение времени, которое не является конечным, а определяется ординальным числом. Для вычислений, выполняемых бесконечное время, необходимы специальные «предельные правила» для определения состояния машины в конце трансфинитного вычисления (например, на предельных ординалах). Позволяет шагам вычисления быть пронумерованными трансфинитными ординалами. Может завершать трансфинитные вычисления и использовать их результаты.

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

В 1991 г. Дэвид Дойч в статье «Квантовая механика вблизи замкнутых времениподобных кривых» показал, что в квантовой механике традиционные парадоксы нарушения хронологии не возникают, при условии, чтобы любая квантовая система, выходящая из временной петли, была идентична системе, вошедшей в неё. Квантовая теория полностью согласована в пространствах-временах с ЗВК, что исключает деструктивную положительную обратную связь циркулирующих через червоточину виртуальных частиц, которая является результатом полуклассических вычислений. Частица, возвращающаяся из будущего, возвращается не в свою исходную вселенную, а в параллельную вселенную Эверетта с альтернативной линией времени. Это значит, что машина времени на основе червоточины является теоретическим мостом между параллельными вселенными, обеспечивающим межмировые путешествия (interuniversal travel). В многомировой интерпретации квантовая система, попадая в прошлое, должна эволюционировать так, чтобы её состояние было согласовано с самим собой. Такая модель позволяет строить квантовые вычислительные устройства, которые могут отправлять себе в прошлое результаты вычислений. По мере развития событий вдоль кольцевой временной шкалы, составляющей ЗВК, никогда не возникнет никаких парадоксов, и этот факт можно использовать для программирования компьютера, который зацикливается внутри ЗВК для решения сложных задач. Если предписание Дойча выполняется, существование этих ЗВК подразумевает эквивалентность квантовых и классических вычислений в классе PSPACE. Доступ к ЗВК может позволить быстро решать PSPACE-полные задачи, класс сложности которых, хотя и разрешим по Тьюрингу, обычно считается вычислительно неразрешимым, поскольку на классическом компьютере требует полиномиального увеличения памяти и экспоненциального времени. Все NP‑полные задачи (SAT, коммивояжёр, раскраска графа и т.д.) становятся тривиально решаемыми. По сути ЗВК делают время и пространство взаимозаменяемыми вычислительными ресурсами.

В 2009 г. Скотт Ааронсон и Джон Уотроус показали, что квантовый компьютер с доступом к ЗВК может решать все задачи класса PSPACE, включая те, что сложнее NP-полных, за полиномиальное время. То есть задачи, решаемые классическим компьютером с использованием памяти полиномиального размера за экспоненциальное время, становятся решаемыми быстро. Более того, как исследовал Скотт Ааронсон, один кубит, имеющий доступ к ЗВК, теоретически может хранить неограниченное количество классической информации, нарушая стандартные информационно-теоретические ограничения, ограничивающие как классические, так и квантовые вычисления. Возможность различать неортогональные состояния поставила бы под угрозу квантовые криптографические протоколы, такие как BB84, безопасность которых основана на фундаментальной неразличимости определённых квантовых состояний. Однако ЗВК не помогут решить ничего за пределами класса PSPACE, то есть квантовая машина времени не является настоящим гиперкомпьютером. Квантовый компьютер ничто не мешает вернуть назад во времени, поскольку все квантовые алгоритмы обратимы. Но если вернуть во времени классический компьютер, мы получим гипервычисление. В некоторых «сильных» моделях ЗВК‑компьютер может вычислять даже невычислимые функции, такие как число Хайтина Ω или Busy Beaver, но такие модели не гарантируют самосогласованность. Теоретически возможны макроскопические червоточины, соединяющие удалённые области пространства-времени с образованием ЗВК, но для их стабилизации необходима экзотическая материя (отрицательная энергия-масса или отталкивающая гравитация), существование которой в макроскопических количествах не подтверждено.

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

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

Леонард Сасскинд на основе статьи Adam Bouland, Bill Fefferman, Umesh Vazirani предложил интересный мысленный эксперимент как исследование возможностей нового класса сложности, который он назвал «JI/poly», где JI означает «Jumping In» («прыгнуть в чёрную дыру»). На самом деле речь идёт о прыжке не в чёрную дыру как таковую, а в квантовый компьютер, моделирующий конформную теорию поля, дуальную объёмной вселенной анти-деСиттера, содержащей чёрную дыру, но эти тонкости можно опустить. Итак, мы берём два сильно запутанных квантовых компьютера, что согласно гипотезе ER=EPR можно описать как червоточину. Коллапсируем один из компьютеров в чёрную дыру и помещаем на её орбиту обычный компьютер, решающий задачу остановки. Алиса может прыгнуть в чёрную дыру и узнать ответ, но она не вернётся назад и не сообщит ответ никому снаружи. К счастью, у неё есть второй квантовый компьютер, запутанный с чёрной дырой. Извлечь ответ из чёрной дыры на нём не получится, поскольку это NP-трудная задача, занимающая экспоненциальное время даже на квантовом компьютере. Однако Алиса идёт на риск и загружает своё оцифрованное сознание в квантовый компьютер, предварительно попросив оставшегося снаружи Боба выполнить операцию запутывания её кубитов с кубитами информации чёрной дыры. Таким образом, она получит субъективный опыт падения в чёрную дыру и узнает ответ на неразрешимую задачу. Если бы ей удалось ещё и выбраться из квантового компьютера, это было бы эквивалентно квантовому алгоритму субэкспоненциального времени для различения случайных и псевдослучайных состояний. Увы, на расшифровку полученного Алисой ответа потребуется экспоненциальное время, как и в случае с расшифровкой излучения Хокинга. Хотя квантовые алгоритмы в принципе обратимы, и Алису можно достать из симуляции за полиномиальное время, но только при условии, что она забудет ответ на задачу остановки! Таким образом, знать ответ можно лишь находясь под горизонтом событий или в симулированной чёрной дыре, а для сообщения его наружу потребуется другой гиперкомпьютер.

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

7. Антропный гиперкомпьютер – использование антропного принципа (мы наблюдаем только те миры, где мы существуем) как фильтра для вычислений. Идея, предложенная в 1990-х гг. Скоттом Ааронсоном и основанная на многомировой интерпретации квантовой механики с дополнительным предположением о квантовом бессмертии наблюдателя. Она аналогична мысленному эксперименту «квантовое самоубийство», только наблюдатель связывает своё существование с правильным ответом на неразрешимую задачу. Запускается недетерминированный процесс вычисления, который может привести к разным исходам в разных мирах, но наблюдатель гарантированно выживает только в тех мирах, где получен нужный результат. В итоге наблюдатель субъективно всегда оказывается в мире, где гипервычисление выполнено, но никому другому он это доказать не сможет. Чтобы устранить субъективизм и обойти проблему меры ветвей, был придуман шуточный алгоритм под названием «квантовый богосорт» (Quantum Bogosort), реализующий многомировую версию обычного богосорта («перетасуй и проверь»). Он делает случайную перестановку входных данных, используя квантовый источник энтропии; затем проверяет, отсортирован ли список; и, если список не отсортирован, уничтожает вселенную. Запуск этого алгоритма приведёт к тому, что как минимум в одной выжившей вселенной входные данные будут успешно отсортированы за полиномиальное время. Естественно, на практике не существует механизма, который уничтожает вселенные или отсекает ветви универсальной волновой функции, поэтому для решения неразрешимой задачи нужно гарантированно получить ответ во всех ветках. К счастью, есть вполне рабочий и безопасный квантовый алгоритм Гровера, решающий NP-полные задачи методом перебора быстрее, чем классические алгоритмы.

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

9. Аналоговая рекуррентная нейросеть (ARNN) Хавы Зигельман. Математическая модель нейросети с невычислимыми действительными весами, способной выполнять гипервычисления в нерекурсивных языках. Представляет собой динамическую систему, развивающуюся в непрерывном фазовом пространстве, в отличие от дискретно-пространственной модели цифровых компьютеров. Она интерпретирует динамическое поведение хаотических биологических систем, не поддающихся описанию стандартными средствами (сердце, мозг) как процесс вычисления и превосходит цифровые вычисления, оставаясь при этом чувствительной к ограничениям ресурсов. В начале 1990-х годов Хава Зигельман и Эдуардо Зонтаг математически доказали, что ARNN обладают определёнными вычислительными возможностями, расширяющими возможности классической универсальной машины Тьюринга. Аналогичным образом, нейросеть, в весовую функцию которой каким-то образом встроено точное значение константы Хайтина, сможет решить проблему остановки, но при этом столкнётся с теми же физическими трудностями, что и другие модели гиперкомпьютеров, основанные на вещественных вычислениях. Христос Пападимитриу, профессор компьютерных наук Калифорнийского университета в Беркли, отметил, что физические системы вполне могут принимать иррациональные значения: «даже стержень длиной, равной невычислимому числу, не является тьюринговым». Однако, «интересный вопрос заключается в том, могут ли такие системы быть эффективно использованы в вычислениях. Я так не думаю. Как изготовить такой стержень и как прочитать его тысячную цифру?».

Фальсифицируемость гипервычислений

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

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

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

Танер Эдис и Маартен Баундри утверждают, что вычислительный процесс в рамках тезиса Чёрча-Тьюринга является естественным, а гипервычислительный процесс за пределами Чёрча-Тьюринга был бы сверхъестественным. «Занимаясь физикой, мы имеем доступ только к конечным вычислительным ресурсам […] Ничто из того, что делают физики, не требует использования бесконечного количества бит памяти или бесконечного количества шагов в вычислениях». Можно возразить: тот факт, что наш сознательный процесс мышления является конечным, последовательным процессом, не означает, что система, более мощная в вычислительном отношении, чем машина Тьюринга, была бы сверхъестественной. Но у нас есть более продвинутые машины Тьюринга, чем биологический мозг – суперкомпьютеры и квантовые компьютеры. Они решают задачи гораздо эффективнее и теоретически могут достичь пределов по энергопотреблению, компактности ячеек памяти и скорости вычислений. Но даже работая на пределе своих возможностей, эти компьютеры не способны на гипервычисления. На сегодняшний день нам неизвестны физические механизмы, которые позволяли бы реализовать вычисление на планковских масштабах, или на околосветовых скоростях, или за сверхкороткие промежутки времени. Если бы теория квантовой гравитации допускала такие вычисления и предсказывала гиперкомпьютер, тогда мы считали бы его естественным.

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

Интероперабельность как основа универсальности

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

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

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

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

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

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

Интероперабельность информации также согласуется с выводами математика Дэвида Вулперта, о которых я рассказывал в статье «Квантовая случайность против детерминизма». Вулперт формализовал аргумент, известный как No Free Lunch for Omniscience («нет бесплатного обеда для всеведения»): никакой интеллект в принципе не может знать всё о Вселенной, частью которой он является. Математик определил «машину вывода» как сверхъестественное всезнающее существо (Демон Лапласа) или учёного, вооружённого суперкомпьютером с неограниченными вычислительными возможностями. Далее он доказал «теорему о монотеизме» (в одной и той же Вселенной не могут сосуществовать две машины вывода) и «теорему о деизме» (одну и ту же машину вывода в разные моменты времени следует рассматривать как две разные машины вывода, сосуществующие в одной и той же Вселенной), из которых следует, что машина вывода не может существовать всегда, а только в определённый момент времени – например, в начале Вселенной.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вывод

Мой вывод по теме более чем оптимистичен: мир объективно реален и познаваем, пусть и не во всей полноте. Физический принцип Чёрча-Тьюринга даёт основание считать, что физический мир познаваем и причинно замкнут, а его законы универсальны. Вера в реальность сверхъестественного, непостижимого, немыслимого, невычислимого, невообразимого и логически невозможного, равно как и вера в существование гиперкомпьютера или сверхразума в пределах нашей вселенной, противоречит принципам интероперабельности и универсальности вычислений. Однако непознанное (ignoramus) не равно непознаваемому (ignoramibus). То, что мы чего-то не знаем, не значит, что это нельзя узнать в принципе. Непознанное физично и может быть вычислено машиной Тьюринга. Непознаваемое находится не только за гранью нашего понимания, но и вне репертуара универсальной машины Тьюринга, и за пределами физического мира – оно несовместимо с нашими законами физики, логики и математики, поэтому не может быть причинно связано с нашей Вселенной. Наша реальность рекурсивно самоподобна: часть вселенной может симулировать любую другую её часть. Возможность существования в нашей вселенной универсального компьютера исключает возможность существования ещё одного компьютера с другим репертуаром – так же, как существование компьютера из барионного вещества исключает существование компьютера из тёмной материи или из антиматерии.

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

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