Профессор MIT Эрик Демэйн и его студенты (Хаяши Ани, Холден Холл, Рикардо Руис, Навин Венкат) доказали, что Super Mario принадлежит к классу сложности RE-Complete, самому сложному классу задач, которые вообще существуют. Демэйн ранее считал, что игра в классе PSPACE, но новая работа переместила её выше. Студенты использовали редакторы уровней Super Mario Maker для создания уровней с 'counter gadgets', системами, отслеживающими Гумб в уровне. Гумба добавляется или удаляется при попадании трубы или прыжке Марио. Система может иметь бесконечное количество Гумб, но размер уровня остаётся конечным, это позволяет симулировать универсальный компьютер (как счётные машины Мински 1961). Если можно построить такую машину внутри уровня, значит можно симулировать ЛЮБОЙ алгоритм: вычислить налоги, скомпилировать код, запустить LLM, решать судоку, доказывать теоремы.
Ключевые факты
- Super Mario поднялся с класса PSPACE в RE-Complete, неразрешимые задачи вроде проблемы остановки Тьюринга
- Используется техника 'гаджетов', локальные компоненты уровня (двери, счётчики), которые кодируют логику
- Counter-гаджеты отслеживают Гумб как числа; количество может быть бесконечным при конечном размере уровня
- Эквивалентно счётным машинам Мински, теоретически универсальным компьютерам; любая такая машина неразрешима
- На практике: теория 'гаджетов' переносится на робо-планирование траекторий и моделирование химических сетей
Ред.: чтобы доказать неразрешимость Super Mario, понадобились бесконечные Гумбы в конечном уровне и счётные машины Мински из 1961 года. В Super Mario Maker вложили больше теории вычислимости, чем Nintendo планировала.
Почему это важно
Это фундаментальный результат теории вычислимости, доказывающий границы того, что компьютеры могут вычислить. Если задача RE-Complete, то не существует алгоритма, который для любого входа корректно предскажет решение (как проблема остановки Тьюринга 1936). Super Mario становится естественным примером такой задачи в популярной культуре.
Ред.: фундаментальный результат теории сложности, поданный через Марио, это лучший способ объяснить проблему остановки тем, кто проблему остановки никогда не остановит.
Кому это важно
Исследователям теории вычислительной сложности, компьютерным учёным, преподавателям информатики. Разработчикам игр (понимание вычислительной сложности уровней). Исследователям robotics и моделирования систем. Любителям видеоигр, интересующимся математикой.
Ред.: теоретикам сложности и геймерам, которые любят математику. Пересечение узкое, но именно оно и аплодирует громче всех.
Как это применить
Техника 'гаджетов' используется для доказательства неразрешимости новых задач (правило: построить в задаче counter-гаджет). На практике результат показывает, где невозможно найти полиномиальный алгоритм, стоит переходить на эвристики, приблизительные методы, или переформулировать задачу.
Ред.: практический вывод честен до боли, если задача RE-Complete, полиномиального алгоритма не ищите, берите эвристики и смиритесь. Марио просто доставил эту новость нагляднее учебника.
Можно ли доверять
MIT Technology Review, работа профессора Демэйна (MacArthur fellow 2001), студентов из MIT. Результаты из курса 'Algorithmic Lower Bounds: Fun with Hardness Proofs'. Техника redaction хорошо известна в CS.
Ред.: профессор-MacArthur, студенты MIT, курс с названием «Fun with Hardness Proofs». Доверять можно, веселья в названии больше, чем в самом доказательстве.
Риски и подводные камни
Результат касается теории, а не практических уровней игры (которые разработаны конечно и обычно не содержат counter-гаджетов). Это не говорит о сложности прохождения обычного Super Mario, только о том, что можно создать синтетический уровень, неразрешимый в теории. Важность за пределами академии пока неясна.
Ред.: важная оговорка, обычные уровни 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
Источник: MIT Technology Review