Super Mario скрывает неожиданную математическую сложность: игра как универсальный компьютер

Команда исследователей из MIT, возглавляемая профессором Эриком Демейном, доказала, что классическая игра Super Mario обладает свойствами, которые делают ее математически неразрешимой. Ученые показали, что игровые уровни способны моделировать работу произвольного компьютера, что ставит их в один ряд с фундаментальными проблемами теории вычислений, такими как проблема остановки.

В основе исследования лежит концепция «гаджетов» — локальных участков игрового уровня, которые функционируют как логические элементы. Например, дверь в игре может быть открыта или закрыта в зависимости от положения врага (Spiny), что позволяет моделировать истинные или ложные утверждения. Комбинируя такие элементы, исследователи создали счетчики, способные хранить и обрабатывать данные, подобно памяти компьютера.

Особенность открытия заключается в том, что даже при ограниченном размере уровня количество монстров и препятствий может быть бесконечным, что позволяет моделировать компьютер с неограниченной памятью. Это означает, что теоретически уровни Super Mario можно использовать для решения любых вычислительных задач: от оптимизации расписаний до доказательства математических теорем или даже работы с большими языковыми моделями (LLM).

Результаты работы подчеркивают, что даже простые на первый взгляд игры могут скрывать сложные математические структуры. Исследование также расширяет понимание границ вычислимости и демонстрирует, как игровые механики могут применяться для моделирования реальных вычислительных процессов.