Один-единственный шар, катающийся по бильярдному столу особой формы, теоретически может выполнить любое вычисление — то есть работает как универсальный компьютер. Математики строго доказали, что такой стол эквивалентен машине Тьюринга. Работа опубликована в журнале Proceedings of the National Academy of Sciences.
Идею «бильярдных вычислений» обсуждали и раньше, но прежние модели требовали множества шаров, трехмерных конструкций или движущихся стенок. Ева Миранда из Политехнического университета Каталонии и Исаак Рамос из Швейцарской высшей технической школы Цюриха убрали все лишнее, оставив чистую геометрию: «программа — это форма стенок, а алгоритм — буквально траектория шара».
Положение шара кодирует информацию, а форма бортов задает шаги вычисления. При этом система наследует и фундаментальные ограничения машины Тьюринга — например, неразрешимую «проблему остановки»: заранее нельзя определить, завершится ли вычисление или шар будет катиться бесконечно.
Это красивый теоретический результат, а не проект реального устройства. Чтобы такой «бильярдный компьютер» работал, нужна бесконечная точность запуска и идеально гладкие борта, чего в физическом мире добиться невозможно: малейшая ошибка в начальном ударе со временем нарастает и сбивает всю траекторию. Ценность работы в другом — она показывает, как удивительно простая механическая система может скрывать всю мощь и все парадоксы вычислимости, связывая геометрию, динамику и теорию алгоритмов.
Машина Тьюринга — это математическая модель любого компьютера, придуманная еще в 1930-х годах: если некое устройство способно воспроизвести ее работу, оно в принципе может вычислить все, что вообще вычислимо. Показав, что на это способен даже один шар на столе правильной формы, авторы продолжают традицию поиска «универсальных вычислителей» в самых неожиданных системах — от клеточных автоматов до потоков жидкости.
Ранее инженер объяснил, почему орбитальные дата-центры пока не актуальны для России.