Математики подтвердили: одного шара, отскакивающего от стен стола особой формы, достаточно для моделирования любого алгоритма. Форма стен представляет собой программу, а траектория — код.
Исследователи Ева Миранда из Политехнического университета Каталонии и Исаак Рамос из ETH Цюрих опубликовали в журнале Proceedings of the National Academy of Sciences свое открытие: один шар, отскакивающий от стен бильярдного стола уникальной формы, способен моделировать универсальную машину Тьюринга — устройство, способное выполнить любой алгоритм. Это исследование решает вопрос, который был поднят математиком Кристофером Муром ещё в 1990 году.
Основой механизма является геометрия. Конфигурация стен кодирует программу, а позиция шара на специальных участках стола служит данными, которые она обрабатывает. Параболические стены перемещают «читающую головку» на одну ячейку памяти, а кривые с бесконечно мелкими осцилляциями обеспечивают чтение и запись символов. «Программа — это форма стен. Алгоритм — это, по сути, траектория шара», — отметила Миранда в публикации исследовательского центра CRM.
Физически создать такой стол невозможно: он требует стен с бесконечно сложной геометрией, а модель предполагает идеально упругие столкновения без трения. Это математический объект, а не инженерная конструкция. Существенно, что теоретический вывод указывает на то, что вычислительная универсальность встроена в законы классической механики — без квантовых эффектов и электроники.
Доказательство также освещает природу непредсказуемости в физических системах. Хаос создает барьер точности: для предсказания траектории требуется экспоненциально растущий объем информации. Алгоритмическая неразрешимость является более принципиальной: никакая программа не сможет ответить на вопрос, попадет ли шар в определенную область или будет ли его траектория периодической. Это напрямую вытекает из теоремы Тьюринга об остановке — основополагающего результата, который определяет пределы всех алгоритмов.
Авторы уже поставили новые вопросы: сколько планет необходимо гравитационной системе, чтобы она могла «вычислять»? Сохраняется ли неразрешимость, если перейти к квантовой механике?
Фото: hi-tech.mail.ru