Хаос «нового уровня» определяет истинный предел предсказуемости

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

Введение

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

Один из ударов пришёлся на начало XX века, с открытием квантовой механики. Когда квантовые частицы не измеряются, они существуют в принципиально размытом мире возможностей. У них нет точного положения, которое мог бы знать демон.

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

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

«Я даю вам точку зрения Бога», — сказал Тоби Кьюбитт, физик, ставший специалистом по информатике в Университетском колледже Лондона, и один из авангардов нынешней атаки на непознаваемое, — «и вы все равно не сможете предсказать, что он сделает».

Ева Миранда, математик из Политехнического университета Каталонии (UPC) в Испании, называет неразрешимость «хаотичной вещью следующего уровня».

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

Эти примеры «накладывают серьёзные ограничения на то, что мы, люди, можем придумать», — сказал Дэвид Уолперт, исследователь из Института Санта-Фе, изучающий пределы познания, но не принимавший участия в недавнем исследовании. «И они неприкосновенны».

Самая черная из коробок

Яркий пример непознаваемости появился в физике в 1990 году, когда Крис Мур, тогда аспирант Корнелльского университета, спроектировал неразрешимую машину с одной движущейся частью.

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

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

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

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

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

Затем расположение бамперов направляет шарик в новые позиции, что соответствует чтению и записи на ленте машины Тьюринга. Некоторые изогнутые бамперы сдвигают ленту в одну сторону, делая данные, хранящиеся в дальних десятичных разрядах, более значимыми, напоминая хаотические системы, в то время как бамперы противоположной кривизны делают это в обратном направлении. Выход шарика из нижней части коробки означает завершение вычисления, результатом которого является конечное положение.

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

Некоторые алгоритмы останавливаются, выдавая результат. Но другие работают вечно. (Представьте себе программу, которой поручено вывести последнюю цифру числа «пи».) Существует ли процедура, спросил Тьюринг, которая может проверить любую программу и определить, остановится ли она? Этот вопрос стал известен как проблема остановки.

Тьюринг показал, что такой процедуры не существует, рассмотрев, что бы это значило. Если бы одна машина могла предсказывать поведение другой, можно было бы легко модифицировать первую машину — ту, которая предсказывает поведение — так, чтобы она работала вечно, когда другая машина останавливается. И наоборот: она останавливается, когда другая машина работает вечно. Затем — и вот что самое интересное — Тьюринг представил, как он вкладывает описание этой модифицированной прогностической машины в саму себя. Если машина останавливается, она также работает вечно. А если она работает вечно, она тоже останавливается. Поскольку ни один из вариантов невозможен, заключил Тьюринг, сама прогностическая машина не должна существовать.

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

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

«Мы знаем, что существуют такие начальные состояния, относительно которых мы не можем заранее предсказать, что из них получится», — сказал Вулперт.

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

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

«Это немного более драматично, — сказал Давид Перес-Гарсия, математик из Мадридского университета Комплутенсе. — Даже имея бесконечные ресурсы, вы не сможете написать программу, решающую эту задачу».

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

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

Получив докторскую степень по физике, Кьюбитт переключился на математику и информатику. Но он никогда не забывал об автомате для игры в пинбол и о том, как информатика накладывает ограничения на физические возможности этого автомата. Он задавался вопросом, затрагивает ли неразрешимость какие-либо действительно важные физические проблемы. За последнее десятилетие он обнаружил, что да.

Современные таинственные материалы

В 2012 году Кьюбитт поставил неразрешимость на путь столкновения с большими квантовыми системами.

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

«Всё началось как шутка. Потом мы начали придумывать идеи», — сказал Перес-Гарсия.

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

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

За следующие три года они выдали 144 страницы насыщенной математики, объединив несколько важных результатов, полученных за предыдущие полвека развития математики и физики. Идея заключалась в том, чтобы использовать квантовые частицы в плоском материале — по сути, в сетке атомов — в качестве заменителя ленты машины Тьюринга.

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

Наконец, используя методы квантовых вычислений, они экспериментировали с взаимодействиями между частицами таким образом, что если суперпозиция представляла собой останавливающееся вычисление, у материала появлялась энергетическая щель. А если вычисление продолжалось бесконечно, у материала не было щели. В статье, опубликованной в журнале Nature в 2015 году, они доказали, что проблема спектральной щели эквивалентна проблеме остановки и, следовательно, неразрешима. Если бы кто-то дал вам полное описание частиц материала, щель либо была бы, либо нет. Но вычислить это свойство математически, исходя из того, как взаимодействуют частицы, было бы невозможно, даже имея квантовый суперкомпьютер 3000 года.

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

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

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

Сираиси сказал: «Если вы будете мыслить слишком обобщенно, вас ждет неудача».

Жидкости, которые вычисляют

Недавно исследователи обнаружили ряд новых ограничений предсказуемости за пределами квантовой физики.

Миранда из Университета Полинезии в Коннектикуте последние несколько лет пыталась выяснить, могут ли жидкости действовать как компьютеры. В 2014 году математик Теренс Тао отметил, что если бы это было возможно, то, возможно, жидкость можно было бы запрограммировать на плеск именно таким образом, чтобы вызвать цунами неограниченной силы. Такое цунами было бы нефизическим, поскольку ни одна волна не может вместить бесконечную энергию в реальном мире. Поэтому любой, кто нашёл бы такой алгоритм, доказал бы, что теория жидкостей, называемая уравнениями Навье-Стокса, предсказывает невозможное — ещё одна задача на миллион долларов.

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

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

А с машинами Тьюринга приходит неразрешимость. В данном случае останавливающееся вычисление соответствует течению, несущему утку в определённое место, а бесконечное вычисление соответствует утке, которая постоянно избегает этого места. Таким образом, как показала группа в публикации 2021 года, определить окончательную судьбу утки было невозможно.

Вычисления в реальности

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

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

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

«Идеального знания не существует, потому что его нельзя потрогать», — сказал Карл Свозил, физик на пенсии, связанный с Венским техническим университетом в Австрии.

«Это очень важные результаты. Они очень, очень глубокие», — сказал Уолперт. «Но в конечном счёте они не имеют никакого значения для человека».

Другие физики, однако, подчёркивают, что бесконечные теории представляют собой близкое — и необходимое — приближение к реальному миру. Климатологи и метеорологи проводят компьютерное моделирование, рассматривая океан как непрерывную жидкость, поскольку невозможно проанализировать океан молекула за молекулой. Им нужна бесконечность, чтобы понять конечность. В этом смысле некоторые исследователи считают бесконечность — и неразрешимость — неизбежным аспектом нашей реальности.

«Было бы своего рода солипсизмом утверждать: «Не существует бесконечных проблем, потому что в конечном итоге жизнь конечна», — сказал Мур.

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

«Вы пытаетесь узнать что-то о том, как работает Вселенная или математика, — сказал Кьюбитт. — Тот факт, что эта задача неразрешима, и вы можете это доказать, и есть ответ».

Источник: www.quantamagazine.org