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