🍄 Super Mario признана алгоритмически неразрешимой
Исследователи из MIT Hardness Group доказали, что задача определения проходимости уровня в Super Mario является алгоритмически неразрешимой (undecidable). Игра переведена из класса сложности PSPACE в класс RE-Complete благодаря использованию внутриигровых механик, имитирующих бесконечную память.
🌍 Исследование показывает, что игровые среды могут служить моделями для экстремально сложных вычислительных задач, помогая классифицировать сложность систем в робототехнике и химии.
👤 Это подтверждает, что даже простые игры могут обладать бесконечной вычислительной сложностью, сопоставимой с проблемой остановки Тьюринга.
Источник 1: https://www.technologyreview.com/2026/06/23/1138262/super-mario-is-mathier-than-you-think/