Математики доказали, что один шар на двумерном бильярдном столе специальной формы может выполнить любой алгоритм. Никакой электроники здесь не нужно — вычисления задаёт геометрия стенок, от которых шар отскакивает.
Модель использует идеальный бильярд с точечной частицей. Шар движется прямолинейно, сталкивается со стенкой и отражается по закону геометрической оптики. Авторы подобрали форму границы так, чтобы последовательность столкновений воспроизводила работу универсальной машины Тьюринга.
Машина Тьюринга — математическая модель компьютера с памятью, символами и правилами переходов между состояниями. Универсальная версия может выполнить любой вычислимый алгоритм. Результат показывает принципиальные вычислительные возможности механической системы, но не означает, что такой шар превзойдёт современный процессор.
Логика полностью закодирована в форме стола. Положение шара хранит состояние виртуальной памяти. Отдельные участки границы переводят систему к следующему шагу вычисления. Параболические фрагменты перемещают считывающую головку между ячейками, более сложные поверхности читают и меняют символы.
Построить такой стол физически невозможно. Некоторые части границы содержали бы бесконечное число всё мельчайших деталей, а начальное положение шара пришлось бы задавать с абсолютной точностью. Это прежде всего математическое доказательство, а не проект механического компьютера.
Работа касается проблемы остановки. Для произвольной программы невозможно создать универсальный алгоритм, который всегда определит заранее, завершится расчёт или будет идти бесконечно. Бильярдная модель наследует то же ограничение.
Когда смоделированная программа заканчивает работу, шар в определённый момент ударяется о специальный участок стены перпендикулярно, разворачивается и проходит прежний путь в обратном направлении. Движение становится периодическим. Если вычисление не завершается, замкнутой траектории не возникает.
Отсюда вытекает необычное следствие: нельзя написать один алгоритм, который для любого такого стола и любых допустимых начальных условий безошибочно определит, периодична ли траектория или шар попадёт в заданную область. Для конкретных случаев ответ возможен, но общего метода для всех конфигураций не существует.
Это ограничение отличается от обычного хаоса. В хаотических системах дальний прогноз рушится, потому что малейшая ошибка в начальных данных со временем растёт. Здесь проблема глубже: даже если начальное состояние известно идеально, может не быть алгоритма, способного ответить на некоторые вопросы о будущем движении.
Бильярдные системы применялись как модели вычислений и раньше, но прежним схемам часто нужны были несколько шаров, дополнительные механизмы или более сложная геометрия пространства. Новая конструкция обходится одной частицей и неподвижной границей. Она показывает, насколько сложное поведение скрывается за очень простыми законами движения.
