ИИтог

Уровни Super Mario оказались неразрешимыми в теории вычислимости

исследованияРедакция ИИтогMIT Technology Review🔥45Рейтинг ИИтог · значимость 45
Уровни Super Mario оказались неразрешимыми в теории вычислимости

Профессор MIT Эрик Демэйн и его студенты (Хаяши Ани, Холден Холл, Рикардо Руис, Навин Венкат) доказали, что Super Mario принадлежит к классу сложности RE-Complete, самому сложному классу задач, которые вообще существуют. Демэйн ранее считал, что игра в классе PSPACE, но новая работа переместила её выше. Студенты использовали редакторы уровней Super Mario Maker для создания уровней с 'counter gadgets', системами, отслеживающими Гумб в уровне. Гумба добавляется или удаляется при попадании трубы или прыжке Марио. Система может иметь бесконечное количество Гумб, но размер уровня остаётся конечным, это позволяет симулировать универсальный компьютер (как счётные машины Мински 1961). Если можно построить такую машину внутри уровня, значит можно симулировать ЛЮБОЙ алгоритм: вычислить налоги, скомпилировать код, запустить LLM, решать судоку, доказывать теоремы.

Ключевые факты

  • Super Mario поднялся с класса PSPACE в RE-Complete, неразрешимые задачи вроде проблемы остановки Тьюринга
  • Используется техника 'гаджетов', локальные компоненты уровня (двери, счётчики), которые кодируют логику
  • Counter-гаджеты отслеживают Гумб как числа; количество может быть бесконечным при конечном размере уровня
  • Эквивалентно счётным машинам Мински, теоретически универсальным компьютерам; любая такая машина неразрешима
  • На практике: теория 'гаджетов' переносится на робо-планирование траекторий и моделирование химических сетей

Почему это важно

Это фундаментальный результат теории вычислимости, доказывающий границы того, что компьютеры могут вычислить. Если задача RE-Complete, то не существует алгоритма, который для любого входа корректно предскажет решение (как проблема остановки Тьюринга 1936). Super Mario становится естественным примером такой задачи в популярной культуре.

Кому это важно

Исследователям теории вычислительной сложности, компьютерным учёным, преподавателям информатики. Разработчикам игр (понимание вычислительной сложности уровней). Исследователям robotics и моделирования систем. Любителям видеоигр, интересующимся математикой.

Как это применить

Техника 'гаджетов' используется для доказательства неразрешимости новых задач (правило: построить в задаче counter-гаджет). На практике результат показывает, где невозможно найти полиномиальный алгоритм, стоит переходить на эвристики, приблизительные методы, или переформулировать задачу.

Можно ли доверять

MIT Technology Review, работа профессора Демэйна (MacArthur fellow 2001), студентов из MIT. Результаты из курса 'Algorithmic Lower Bounds: Fun with Hardness Proofs'. Техника redaction хорошо известна в CS.

Риски и подводные камни

Результат касается теории, а не практических уровней игры (которые разработаны конечно и обычно не содержат counter-гаджетов). Это не говорит о сложности прохождения обычного Super Mario, только о том, что можно создать синтетический уровень, неразрешимый в теории. Важность за пределами академии пока неясна.

«If you can build a machine with even just a few of those counters, you can simulate an arbitrary computer, one that could essentially do anything a non-quantum computer could do»

— Эрик Демэйн, профессор MIT