Математики превратили бильярдный шар в универсальный компьютер — теоретически

Хорошие новости: ему не нужны чипы памяти. Плохие новости: построить такой компьютер все равно не получится.

Математики Ева Миранда из Политехнического университета Каталонии и Исаак Рамос из ETH Zurich показали, что один шар в специально спроектированном двумерном бильярде способен имитировать машину Тьюринга. Простая механическая система теоретически может выполнять любые вычисления, описываемые алгоритмом.

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

В модели исследователей информация кодируется положением шара, а роль программы выполняет форма неподвижных стенок. Шар-частица движется по прямой, отражается от границ и шаг за шагом меняет свое состояние; таким образом, вся логика вычисления оказывается записана в геометрии пространства.

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

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

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