Исследователи из MIT Hardness Group доказали, что задача определения проходимости уровня в Super Mario является алгоритмически неразрешимой. Это открытие переводит сложность игры из класса PSPACE в класс RE-Complete, что математически приравнивает ее к фундаментальным проблемам информатики, таким как проблема остановки Тьюринга.
Что произошло
Ученые из MIT Hardness Group установили, что создание программы, которая могла бы всегда предсказывать успешное прохождение любого уровня Super Mario, невозможно. Доказательство основано на использовании игровых механик для создания вычислительных «гаджетов», в частности счетчика Минского на базе врагов Goombas, который имитирует бесконечно расширяемую память.
Контекст
Ранее задача классифицировалась как относящаяся к классу сложности PSPACE. Однако обнаружение возможности моделирования полноценных вычислительных систем внутри игрового движка позволило перевести игру в класс RE-Complete, что делает задачу определения проходимости undecidable (неразрешимой).
Почему это важно для индустрии
Исследование открывает возможности использования игровых сред для моделирования экстремально сложных вычислительных задач. Теория «гаджетов», примененная в работе, может помочь классифицировать сложность систем в таких областях, как робототехника и химия, а также служить полигоном для проверки вычислительной устойчивости новых архитектур и алгоритмов.
Почему это важно для пользователей
Для широкой аудитории и специалистов это подтверждение того, что даже простые на вид интерактивные системы могут скрывать в себе бесконечную вычислительную сложность. Это меняет взгляд на игровые движки: из инструментов развлечения они превращаются в мощные модели для исследования теоретических пределов автоматизации.
Что пока неизвестно / ограничения
Существует различие в оценке практической значимости: в то время как исследователи видят в этом мощный инструмент для моделирования, enterprise-архитекторы проявляют скептицизм относительно прямого применения данных выводов в текущих корпоративных AI-решениях без узкоспециализированных задач.
Источники
Автор
Look at AI, редакция