Один бильярдный шар теоретически способен произвести любое вычисление

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

Как доказали математики Ева Миранда из Политехнического университета Каталонии и Исаак Рамос из Швейцарской высшей технической школы Цюриха, единственный шар, рикошетящий внутри плоского «бильярда» особой конфигурации, способен имитировать универсальную машину Тьюринга — абстрактное устройство, способное воспроизводить логику любой другой аналогичной машины.

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

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

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

Миранда и Рамос отыскали способ воссоздать логику Тьюринга за счёт чистой геометрии и движущегося шара.

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

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

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

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

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

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

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

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

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

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

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

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

Результаты исследования опубликованы на страницах Proceedings of the National Academy of Sciences.

Источник