MIT Proved Super Mario Is Unsolvable. Here's Why That Matters.

MIT Researchers Proved Certain Super Mario Levels Are Undecidable

In 2023, four MIT students in Erik Demaine's complexity theory class built Super Mario levels so difficult that no computer program can ever determine whether they're beatable. The proof pushed Super Mario from PSPACE (solvable but impractically hard) into RE-Complete, the class of undecidable problems.

Demaine, a MacArthur fellow, has spent 14 years studying Super Mario complexity. Earlier work showed the game was harder than the traveling-salesman problem or factoring large numbers. The new result surprised even him: Demaine had called PSPACE Mario's "permanent home."

The students (Hayashi Ani, Holden Hall, Ricardo Ruiz, and Naveen Venkat) used fan-made level editors and Super Mario Maker to construct levels containing what they call "gadgets"—localized patterns that encode true/false logic. A door gadget, for example, uses a Spiny pacing left and right: when the Spiny is on the left, the door is closed; on the right, it opens. This binary state mirrors a true/false value.

The breakthrough came when they designed a "counter gadget" that tracks Goomba counts. Each time a pipe spawns a Goomba or Mario stomps one, the counter increments or decrements. The trick: with no level-size limit, the counter has infinite expandable memory despite the visual level staying the same.

Since Marvin Minsky proved in 1961 that counter machines (which store two numbers and increment/decrement them) are undecidable, and since the gadgets simulate counter machines, any Mario level with a counter gadget is unsolvable. The proof mirrors Alan Turing's Halting Problem: just as no program can predict whether any arbitrary program halts, no program can predict whether any arbitrary Mario level is beatable.

Gadget Theory Is Already Solving Real Problems Outside Games

The Mario research is didactic window dressing. The actual contribution is gadget theory itself.

Fabrizio Grandoni, a complexity researcher at the University of Applied Sciences and Arts of Southern Switzerland, told MIT News in 2016 that "studying video games is interesting mostly for didactical reasons," as a way to attract students to complexity theory. That observation holds. Hall, one of the four students, had minimal prior exposure to complexity theory before the course.

What matters is deployment. Researchers at the University of Texas Rio Grande Valley, including Timothy Gomez (now a PhD student at MIT), have already applied gadget theory to robotic motion planning and chemical reaction networks. Demaine notes the dual use: "It can be used in the negative way to say, 'we should stop searching for algorithms because this problem is too hard'—or in the positive way, because to prove something hard, you're showing you can build a computer of a certain type."

The ability to quickly prove a problem undecidable using gadget templates saves researchers from chasing algorithms that don't exist. In robotics and chemistry, that saves time and budget.

How to Use Gadget Theory If You Work on Hard Problems

If you're tackling motion planning, scheduling, or constraint satisfaction, gadget theory gives you a formal language for proving your problem is actually unsolvable, not just hard to solve.

The standard playbook: convert your problem into a reduction that maps it to a known undecidable problem (like the Halting Problem or Post's Correspondence Problem), then build gadgets that simulate the necessary logical operations. If you succeed, you've proved no algorithm will ever solve the general case. If you fail, you've either found a solvable subclass or need a different approach.

Hall's observation after taking the class is the real takeaway: "I really enjoyed the class, and so I've taken a lot more classes in that realm." Gadget theory is a teachable, reproducible method. It spreads. The Mario levels are just the initial demo.