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

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

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

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

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

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

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

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

Пьер-Симон Лаплас предположил, что всезнающий демон может идеально предсказать будущее любой физической системы. Он ошибался.

Иоганн Эрнст Хейнсиус / Wikimedia Commons

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

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

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

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

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

Я даю вам точку зрения Бога, и вы все равно не можете предсказать, что она сделает.

Тоби Кубитт, Университетский колледж Лондона

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

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

Кристина Армитидж/ Журнал Quanta

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

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

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

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

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

Архив GL/Фото Alamy

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

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

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

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

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

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

Крис Мур разработал одну из самых ранних и простейших неразрешимых физических систем.

Крессандра Тибодо

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

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

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

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

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

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

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

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

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

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

Дэвид Перес-Гарсия (слева) и Тоби Кубитт разработали квантовый материал, состояние которого может охватить любые вычисления, возможные для машины Тьюринга.

Слева направо: Предоставлено Дэвидом Пересом-Гарсией; Джонни Милларом

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

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

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

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

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

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

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

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

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

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

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

Ева Миранда показала, что жидкости могут течь настолько сложным образом, что траектории их движения становятся неразрешимыми.

Хорди Кортада

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

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

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

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

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

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

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

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

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

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

СВЯЗАННЫЙ:

1. С помощью Fifth Busy Beaver исследователи приближаются к пределам вычислений

2. Сколько всего чисел существует? Доказательство бесконечности приближает математику к ответу.

3. Скрытые героини Хаоса

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

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

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

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

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

Комментарии: