Super Mario is mathier than you think

2026-06-23 · Source: MIT Technology Review · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences, Gaming & Interactive Media · Depth: Advanced, medium

Summary

Research from the MIT Hardness Group, a placeholder for theoretical computer science projects from Erik Demaine's class "Algorithmic Lower Bounds: Fun with Hardness Proofs," has revealed that certain Super Mario levels are computationally undecidable. This means no computer program can consistently determine if these levels are beatable. Previously believed to be in the PSPACE complexity class, new findings by students Hayashi Ani '21, MEng '23; Holden Hall '26; Ricardo Ruiz '24, MEng '25; and Naveen Venkat '23, MEng '24 in their 2023 class pushed Super Mario into the RE-Complete class, the hardest complexity class for such games. Their work involved creating complex levels using fan-made editors and Super Mario Maker, employing "gadget theory" and "counter gadgets" to simulate universal counter machines, akin to the Halting Problem. This demonstrates that Super Mario levels can embody the power of any theoretical computer.

Key takeaway

For computational complexity researchers or AI scientists exploring algorithmic limits, this work highlights that even seemingly simple systems like Super Mario can exhibit undecidable properties. You should consider how "gadget theory" and the simulation of universal machines can be applied to prove hardness in other domains, such as robotic motion or chemical reaction networks. This finding underscores the importance of identifying inherent computational boundaries before attempting to develop universal solvers for complex problems.

Key insights

Super Mario levels can be computationally undecidable, simulating universal computers and placing them in the RE-Complete complexity class.

Principles

• Undecidable problems lack universal algorithmic solutions.
• Gadget theory can model complex game mechanics.
• Simulating counter machines proves computational universality.

Method

Researchers used reduction and gadget theory, specifically "door" and "counter" gadgets, within Super Mario Maker to simulate Minsky's universal counter machines, proving undecidability.

In practice

• Apply gadget theory to analyze robotic motion planning.
• Use game-based problems to teach complexity theory.
• Identify computational limits in system design.

Topics

• Computational Complexity
• Undecidability
• Super Mario
• Gadget Theory
• Halting Problem
• Counter Machines

Best for: AI Scientist, Research Scientist, AI Student

Related on AIssential

• The Complexity of Min-Max Optimization for Quadratic Polynomials — Approximating min-max stationary points for quadratic polynomials over hypercubes is PPAD-hard, even under specific constraints.
• In a Sea of Complexity, Does a "Successor" Exist? - with Stephen Wolfram of Wolfram Research — Simple computational rules can generate profound complexity and unpredictability, fundamental to both natural and artificial intelligence.
• Achieving Gold-Medal-Level Olympiad Reasoning via Simple and Unified Scaling — A compact 30B-A3B model achieves Olympiad-level reasoning through a multi-stage training and inference pipeline.
• A "Lay" Introduction to "On the Complexity of Neural Computation in Superposition" — Neural networks achieve representational efficiency through superposition, with specific computational complexity bounds.
• Hinton Won the Nobel Prize for a Math He Says Will Kill Us. Here’s the Equation He’s Afraid Of. — The provided content introduces Geoffrey Hinton's foundational work in machine learning, highlighting his current apprehension regarding the mathematics he developed that enabled machines to learn.
• Subject to: Laureano Escudero — Laureano Escudero's career exemplifies dedication to mathematical optimization and its real-world applications.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by MIT Technology Review.