Трудно представить себе физическую систему проще бильярдного стола. Пустите шар по столу, и его движение будет подчиняться простому правилу: он движется по прямой, пока не ударится о борт, после чего отскочит от него под тем же углом, под каким приблизился. И всё же даже такая простая система — по крайней мере теоретически — способна воспроизвести любое вычисление, доступное гораздо более сложному компьютеру.
Как показали математики Ева Миранда из Политехнического университета Каталонии в Испании и Исаак Рамос из Швейцарской высшей технической школы Цюриха, один шар, отскакивающий от стенок двумерного «бильярда» особой формы, может имитировать универсальную машину Тьюринга — такую, которая способна моделировать любую другую машину Тьюринга.
Для Миранды эта работа стала итогом многолетних попыток свести механическую систему к минимальному числу деталей, необходимому ей для работы в качестве компьютера. «Каков минимальный геометрический механизм, позволяющий физической системе выполнять универсальные вычисления, и как мы можем его обнаружить? — спрашивает она. — Бильярд представляет собой самую суровую проверку такого процесса упрощения. Одна‑единственная частица. Вся программа записана в геометрии границы».
Машина Тьюринга — это не машина в привычном смысле слова. Это математическая модель вычислений, предложенная британским математиком Аланом Тьюрингом в 1936 году. В простейшем виде она состоит из воображаемой ленты, разделённой на ячейки, головки, которая может считывать и записывать символы на этой ленте, и набора инструкций, определяющих её последующие действия. Каждая отдельная операция предельно проста: прочитать символ, записать символ, переместиться вдоль ленты и повторить всё снова.
Универсальная машина Тьюринга идёт ещё дальше: она может имитировать любую другую машину Тьюринга, а значит, теоретически способна выполнить любое вычисление, которое можно выразить в виде алгоритма.
Миранда и Рамос нашли способ воспроизвести работу машины Тьюринга при помощи одной лишь геометрии и отскакивающего шара.
В их математическом «бильярде» — именно этим словом учёные называют свою систему — положение шара может кодировать информацию, а тщательно спроектированная форма стенок определяет, что произойдёт с этой информацией дальше. Когда шар перемещается из одной части бильярда в другую, его траектория продвигает вычисление вперёд — подобно тому как машина Тьюринга шаг за шагом выполняет свои инструкции.
Бильярдные системы связывали с вычислениями и раньше, однако прежним моделям требовались дополнительные усложнения: несколько взаимодействующих шаров, трёхмерные конструкции или движущиеся стенки. Миранда и Рамос отказались от всего этого. Для работы их системы достаточно одной частицы, движущейся в двух измерениях между неподвижными стенками. «Вычисляющий бильярдный стол совсем не похож на компьютер. Он выглядит как плохо нарисованный лабиринт, полный углов и дуг, которые кажутся случайной прихотью, — говорит Миранда. — Программа — это форма стенок. Алгоритм — в буквальном смысле траектория».
Но, превращая бильярдный стол в универсальный компьютер, мы переносим в него не только полезные свойства вычислительной системы. Вместе с ними бильярд наследует и её ограничения. Одно из таких ограничений известно как проблема остановки.
Представим, что компьютер должен определить, завершит ли некоторая программа свою работу или будет выполняться бесконечно. В каждом отдельном случае установить это вполне возможно — например, понять, завершится ли установка обновления операционной системы или преобразование файла.
Однако Тьюринг доказал, что не существует единого алгоритма, способного надёжно ответить на этот вопрос для любой возможной программы и любых входных данных. Предыдущие исследования показали, что это фундаментальное ограничение можно воспроизвести в физических системах с несколькими шарами.
Бильярд Миранды и Рамоса показывает, что его можно воспроизвести и в движении одного‑единственного шара. Чтобы продемонстрировать это, исследователи спроектировали свой бильярд так, чтобы достижение вычислением состояния остановки соответствовало удару шара о стенку под прямым углом, после которого он отправлялся обратно по прежней траектории. Если вычисление никогда не остановится, траектория шара также никогда не повторится. Но если бы существовал алгоритм, способный определить, повторится ли она когда‑нибудь, он мог бы решить проблему остановки, что, как доказал Тьюринг, невозможно.
«Хаос накладывает ограничения на точность, а неразрешимость ставит логический барьер, — говорит Миранда. — Даже если мы в точности знаем уравнения и начальные данные, может не существовать алгоритма, способного определить, попадёт ли когда‑нибудь траектория в заданную область. Это не означает, что каждая отдельная траектория остаётся загадкой. Во многих конкретных случаях мы получим ответ. Невозможно лишь разработать универсальный метод, который позволял бы решить любой такой случай».
Есть веские причины, по которым никто не станет заменять кремниевые микросхемы бильярдными шарами. Эта конструкция представляет собой идеализированную математическую модель, в которой информация кодируется на всё более мелких масштабах. На реальном физическом столе невозможно было бы обеспечить для этого неограниченную точность.
Однако такие бильярдные системы — не просто математические диковинки. Эти теоретические конструкции полезны физикам, поскольку простое движение частицы, отскакивающей от границ, может служить моделью более сложных физических систем — от сталкивающихся частиц газа до систем, поведение которых определяется резко возрастающими удерживающими силами.
«Можно сказать, что они представляют собой своего рода скелет классической механики», — говорит Миранда. Этот скелет может проявляться даже в небесной механике — в частности, в математических описаниях тесных сближений гравитирующих тел, включая разновидности печально известной своей сложностью задачи трёх тел.
Это не означает, что Миранда и Рамос доказали неразрешимость самой задачи трёх тел. Однако их работа ставит вопрос о том, могут ли те же вычислительные ограничения возникать в более реалистичных гравитационных системах, превращая неразрешимость — наряду с хаосом — в ещё один фундаментальный барьер для прогнозирования.
«Сколько планет требуется, чтобы гравитация начала выполнять вычисления? — говорит Миранда. — Сколько их нужно, чтобы возникла неразрешимость? Возможно, три, возможно, пять, а возможно, гораздо больше. Это совершенно открытый вопрос».
Работа опубликована в журнале Proceedings of the National Academy of Sciences.
Автор: SLY_G
