Трудно представить себе физическую систему проще бильярдного стола. Пустите шар по столу, и его движение будет подчиняться простому правилу: он движется по прямой, пока не ударится о борт, после чего отскочит от него под тем же углом, под каким приблизился. И всё же даже такая простая система — по крайней мере теоретически — способна воспроизвести любое вычисление, доступное гораздо более сложному компьютеру.
Как показали математики Ева Миранда из Политехнического университета Каталонии в Испании и Исаак Рамос из Швейцарской высшей технической школы Цюриха, один шар, отскакивающий от стенок двумерного «бильярда» особой формы, может имитировать универсальную машину Тьюринга — такую, которая способна моделировать любую другую машину Тьюринга.
Для Миранды эта работа стала итогом многолетних попыток свести механическую систему к минимальному числу деталей, необходимому ей для работы в качестве компьютера. «Каков минимальный геометрический механизм, позволяющий физической системе выполнять универсальные вычисления, и как мы можем его обнаружить? — спрашивает она. — Бильярд представляет собой самую суровую проверку такого процесса упрощения. Одна‑единственная частица. Вся программа записана в геометрии границы».
Машина Тьюринга — это не машина в привычном смысле слова. Это математическая модель вычислений, предложенная британским математиком Аланом Тьюрингом в 1936 году. В простейшем виде она состоит из воображаемой ленты, разделённой на ячейки, головки, которая может считывать и записывать символы на этой ленте, и набора инструкций, определяющих её последующие действия. Каждая отдельная операция предельно проста: прочитать символ, записать символ, переместиться вдоль ленты и повторить всё снова.
Универсальная машина Тьюринга идёт ещё дальше: она может имитировать любую другую машину Тьюринга, а значит, теоретически способна выполнить любое вычисление, которое можно выразить в виде алгоритма.
Миранда и Рамос нашли способ воспроизвести работу машины Тьюринга при помощи одной лишь геометрии и отскакивающего шара.
В их математическом «бильярде» — именно этим словом учёные называют свою систему — положение шара может кодировать информацию, а тщательно спроектированная форма стенок определяет, что произойдёт с этой информацией дальше. Когда шар перемещается из одной части бильярда в другую, его траектория продвигает вычисление вперёд — подобно тому как машина Тьюринга шаг за шагом выполняет свои инструкции.
Бильярдные системы связывали с вычислениями и раньше, однако прежним моделям требовались дополнительные усложнения: несколько взаимодействующих шаров, трёхмерные конструкции или движущиеся стенки. Миранда и Рамос отказались от всего этого. Для работы их системы достаточно одной частицы, движущейся в двух измерениях между неподвижными стенками. «Вычисляющий бильярдный стол совсем не похож на компьютер. Он выглядит как плохо нарисованный лабиринт, полный углов и дуг, которые кажутся случайной прихотью, — говорит Миранда. — Программа — это форма стенок. Алгоритм — в буквальном смысле траектория».
Но, превращая бильярдный стол в универсальный компьютер, мы переносим в него не только полезные свойства вычислительной системы. Вместе с ними бильярд наследует и её ограничения. Одно из таких ограничений известно как проблема остановки.
Представим, что компьютер должен определить, завершит ли некоторая программа свою работу или будет выполняться бесконечно. В каждом отдельном случае установить это вполне возможно — например, понять, завершится ли установка обновления операционной системы или преобразование файла.
Однако Тьюринг доказал, что не существует единого алгоритма, способного надёжно ответить на этот вопрос для любой возможной программы и любых входных данных. Предыдущие исследования показали, что это фундаментальное ограничение можно воспроизвести в физических системах с несколькими шарами.
Бильярд Миранды и Рамоса показывает, что его можно воспроизвести и в движении одного‑единственного шара. Чтобы продемонстрировать это, исследователи спроектировали свой бильярд так, чтобы достижение вычислением состояния остановки соответствовало удару шара о стенку под прямым углом, после которого он отправлялся обратно по прежней траектории. Если вычисление никогда не остановится, траектория шара также никогда не повторится. Но если бы существовал алгоритм, способный определить, повторится ли она когда‑нибудь, он мог бы решить проблему остановки, что, как доказал Тьюринг, невозможно.
«Хаос накладывает ограничения на точность, а неразрешимость ставит логический барьер, — говорит Миранда. — Даже если мы в точности знаем уравнения и начальные данные, может не существовать алгоритма, способного определить, попадёт ли когда‑нибудь траектория в заданную область. Это не означает, что каждая отдельная траектория остаётся загадкой. Во многих конкретных случаях мы получим ответ. Невозможно лишь разработать универсальный метод, который позволял бы решить любой такой случай».
Есть веские причины, по которым никто не станет заменять кремниевые микросхемы бильярдными шарами. Эта конструкция представляет собой идеализированную математическую модель, в которой информация кодируется на всё более мелких масштабах. На реальном физическом столе невозможно было бы обеспечить для этого неограниченную точность.
Однако такие бильярдные системы — не просто математические диковинки. Эти теоретические конструкции полезны физикам, поскольку простое движение частицы, отскакивающей от границ, может служить моделью более сложных физических систем — от сталкивающихся частиц газа до систем, поведение которых определяется резко возрастающими удерживающими силами.
«Можно сказать, что они представляют собой своего рода скелет классической механики», — говорит Миранда. Этот скелет может проявляться даже в небесной механике — в частности, в математических описаниях тесных сближений гравитирующих тел, включая разновидности печально известной своей сложностью задачи трёх тел.
Это не означает, что Миранда и Рамос доказали неразрешимость самой задачи трёх тел. Однако их работа ставит вопрос о том, могут ли те же вычислительные ограничения возникать в более реалистичных гравитационных системах, превращая неразрешимость — наряду с хаосом — в ещё один фундаментальный барьер для прогнозирования.
«Сколько планет требуется, чтобы гравитация начала выполнять вычисления? — говорит Миранда. — Сколько их нужно, чтобы возникла неразрешимость? Возможно, три, возможно, пять, а возможно, гораздо больше. Это совершенно открытый вопрос».
Работа опубликована в журнале Proceedings of the National Academy of Sciences.
Комментарии (38)
wataru
22.09.2026 10:18Неясно, что ли вся лента машины тьюринга (бесконечная!) закодирована только лишь в положении и скорости шара? Значит там стенки практически фрактальные получаются?
ksbes
22.09.2026 10:18Да, а шар нулевого размера - иначе он все фрактальные неровновности “синтегрирует”.
RaceCondition
22.09.2026 10:18Неясно, что ли вся лента машины тьюринга (бесконечная!) закодирована только лишь в положении и скорости шара?
Закодирована только в положении. Скорость не используется.
CitizenOfDreams
22.09.2026 10:18Любители. Возьмите этот бильярдный шар и бейте им математика, пока он не посчитает что вам нужно.
SadOcean
22.09.2026 10:18Наша вселенная весьма опасна.
Одно неосторожное движение - и у тебя получилась Тьюринг полная херня.
Бесконечность Больцмановских мозгов воет в унисон.
habranon
22.09.2026 10:18Есть веские причины, по которым никто не станет заменять кремниевые микросхемы бильярдными шарами. Эта конструкция представляет собой идеализированную математическую модель, в которой информация кодируется на всё более мелких масштабах. На реальном физическом столе невозможно было бы обеспечить для этого неограниченную точность.
Хм... Какая-то незавершенность. Ну погоняли бы виртуальные шары, вроде мощность железа позволяет это сделать.
niktor_mpt
22.09.2026 10:18Получается, для того, чтобы такой "бильярд" что-то подсчитал, нужно вначале его рассчитать?
Сколько вычислений надо сделать, чтобы построить (определить линию границ) бильярд, решающий "2+2="?
petsernik
22.09.2026 10:18В книжке "Principia mathematica, by Alfred North Whitehead ... and Bertrand Russell." утверждение, что "1+1=2" впервые упоминается на странице 379 :) И то как подготовительная лемма, чтобы затем доказать (но эта лемма считай уже почти всё доказала).
Страница 379, лемма 54.43
Так что бильярд ещё поудобнее будет.
niktor_mpt
22.09.2026 10:18Это они числа в теории множеств определили. Там свои приколы, да.
Множества больше подходят для описания качеств, а не количеств.
А определить число как предельную абстракцию весьма непросто.
Но я не про сложность рассуждений или удобство определения понятия числа и арифметических операций, а про количество вычислений, необходимых для совершения конкретной операции.
rudnyi
22.09.2026 10:18В статье ниже посчитано сколько символов потребуется для записи единицы в системе Бурбаки - получилось замечательное число 4 523 659 424 929. Это только записать единицу.
Adrian RD. Mathias, A Term of Length 4 523 659 424 929. Synthese 133, no. 1 (2002): 75-86.
LinkToOS
22.09.2026 10:18Бильярдные системы связывали с вычислениями и раньше, однако прежним моделям требовались дополнительные усложнения: несколько взаимодействующих шаров, трёхмерные конструкции или движущиеся стенки. Миранда и Рамос отказались от всего этого. Для работы их системы достаточно одной частицы, движущейся в двух измерениях между неподвижными стенками.
Тогда конфигурация лабиринта, и форма стенок, должны быть бесконечно сложными. А это противоречит концепции упрощения.
Единичная операция проста - отскок шара от стенки под углом. Но использовать полученный результат для следующей операции уже сложно. И чем больше последовательных операций, тем сложнее конфигурация.
DrGluck07
Автора этих строк ждёт много интересных открытий, если он пойдет в бильярдную и попробует проверить это все на практике. И угол отскока не тот же самый. И движение не всегда прямолинейное.
k12th
Ну авторы статьи оговариваются, что эта модель для сферического шара в вакууме.
CitizenOfDreams
... в пустотном вакууме?
degor
Гораздо интересней была бы модель для несферического шара.
k12th
Сферическим шаром каждый сумеет, а ты вот от коровы добейся… пятнадцать поросят, понимаешь, добейся, вот это работа!
InsiderCrush
Да что там несферический шар? Даешь 1D бильярд! :D
LinkToOS
Чтобы получить несферический шар, надо на него натянуть сову.
OlegZH
Вообще-то, существует ещё математическая теория бильярдов. Кажется, к этой теории приложили руку В.И.Арнольд и Я.Г.Синай.
rudnyi
При этом у них обыгрывается то, что бильярды являются хорошим примером динамического хаоса. В этом смысле пример, представленный в статье, крайне неудачный, поскольку должен получиться только динамический хаос.
OlegZH
Если б можно было снова поступить на первый курс! Когда голова ещё что-то воспринимала. Сейчас, уже какие-то вещи лучше понимаешь, но, если бы это понимание было уже тогда... Сколько красивых теорий! Можно было бы даже попытаться что-то новое сделать.
Astroscope
Так для этого нужна практика в другом смысле - тренироваться нужно. Конечно, необязательно выходить на уровень чемпионата мира по снукеру (скучная для зрителя, но трудная для игрока "надежная" игра по правильному выставлению белого шара под следующий удар) или пулу (вот где разгул трюковых ударов), чтобы понять и на себе испытать то, о чем вы говорите, но первый или даже десятый, а то и сотый поход в бильярдную рискует, при неаккуратном обращении, скорее закончиться безобидным киксом или более затратным разрывом сукна, чем намеренно не-прямолинейным движением шара с отражением от борта под углом, не равным углу
падениякасания.И не шар вовсе, а плоская - на спинах четырех слонов. Ой, нет, это не про бильярд, простите...
Caterpillar-KZ
Чёй-то снукер скучная, всегда засматривался на игру Ронни.
OlegZH
Скучная? Преулекательнейшая!!
Astroscope
@Caterpillar-KZ @OlegZH
Ну так вы, наверное, любители биллиарда - конечно вам увлекательно (мне тоже мегаувлекательно, но я любитель биллиарда). Для мимокрокодилов же, уверяю, это скукотища.
ksbes
Мне даже интересно стало - какая инра ниболее скучна для мимокрокодилов? Я лично ставлю на гольф!
Astroscope
В этом рейтинге я голосую за бейсбол. Ну, если брать из относительно массовых, конечно, и не считать чемпионаты мира по метанию сотовых телефонов.
Gansterito
Вас, видимо, тоже ждет увлекательный мир математических абстракций)
DrGluck07
Так нужно было сказать что это шарик от Арканоида и вообще никаких вопросов.
SadOcean
Ну очевидно, что речь об абстрактной машине. Еще трение тысяч отскакиваний посчитать
petsernik
Никакая теоретическая модель не моделирует всю практическую реальность абсолютно точно, отклонения какого-либо реального хоть сколько-нибудь серьёзного явления от его теоритечской модели всегда будут.
Более того — система аксиом ZFC либо неполна, либо противоречива, а на ней чуть ли не вся математика и физика держится, и в частности всякие расчёты (по крайней где участвуют вещественные числа).
"Попробуйте на практике показать корень из минус единицы на графике гиперболы", для меня Ваше утверждение созвучно этой фразе, считаю, что не стоит сравнивать сферического коня в вакууме с реальными конями.
Когда речь о теоретической математической модели (то есть о математике), там всегда сферический конь в вакууме, а вот расчёт погрешностей для сравнения с реальностью уже физики/инженеры/механики делают, математикам такое редко будет интересно, они живут абстракциями в своём воображаемом мире, и если математик не хочет заниматься прикладным миром, то и нечего ему указывать на реальность, ему вполне достаточно воображения, системы аксиом и ручки/компьютера, чтобы оставаться в рамках логически непротиворечивых утверждений, не выходя из модели, которую он рассматривает (в предположении непротиворечивости рассматриваемой системы аксиом).
Так что если хотите поспорить с математиком, то уточните модель, которую он рассматривает, а уже потом в рамках этой модели и спорьте, а не ведите его в бильярдную с просьбой показать на практике идеальный удар идеального шара по идеальной поверхности, иначе претензии к математику мягко говоря необоснованны, да и таких идеальных бильярдных не существует.
achekalin
Один редактор Хабра теоретически способен как заполнить любое пустое место, так и запутать читателя до полной нестыковки причины со следствием.
Особенно хорошо получилось здесь:
«В каждом отдельном случае установить это вполне возможно… Однако Тьюринг доказал, что не существует единого алгоритма…»
Нет, «в каждом отдельном случае» установить это как раз не обязательно возможно. Можно решить множество конкретных случаев, а если программа остановится — просто дождаться остановки. Но существуют и конкретные программы, для которых доказать остановку или неостановку мы не умеем.
Проблема остановки говорит не «каждый случай решаем, но все сразу почему-то нет», а о невозможности универсального алгоритма, решающего эту задачу для любой программы и любых входных данных.
Справедливости ради, автор оригинала тоже приложил к этому руку: там стоит довольно опасное «On a case-by-case basis, this is absolutely achievable». Но редактор не стал распутывать неудачное объяснение, а аккуратно перевёл его в состояние окончательной причинно-следственной суперпозиции.