MIT students proved Super Mario levels are undecidable, not just hard

If you think “Super Mario is mathy” just means clever levels and good physics, MIT just changed the scoreboard. In a 2023 class project, Erik Demaine’s students Hayashi Ani (’21, MEng ’23), Holden Hall (’26), Ricardo Ruiz (’24, MEng ’25), and Naveen Venkat (’23, MEng ’24) built Super Mario levels that are provably undecidable. Meaning: there is no computer program that always correctly predicts whether Mario can reach the castle in those levels.

And this is not a vibes-based claim. The work pushed Super Mario out of the PSPACE complexity class Demaine previously treated as its “permanent home” and into RE-Complete, the class of undecidable problems. That shift matters because it redraws the boundary between problems that are solvable in principle (but too expensive in practice) and problems that no algorithm can always answer correctly.

So what exactly did they do to turn a video game into a proof machine? The MIT Hardness Group in the article is a placeholder name for theoretical computer science projects, including several related to Super Mario, tied to Demaine’s course “Algorithmic Lower Bounds: Fun with Hardness Proofs.” Demaine is a computer science professor who also researches complexity theory, the field that sorts problems into categories based on time and memory needed to solve them. He is also an avid Super Mario fan, which explains why he keeps coming back to a game that is basically a playground for formal reasoning.

Super Mario’s structure is part of the reason the theory applies so cleanly. The game is a horizontally scrolling platform world of pipes and platforms where the goal is to rescue Princess Peach, battling enemies like Goombas and deadly porcupines called Spinies. Levels end with a flagpole in the original version, sending Mario onward. Demaine and collaborators have spent roughly the last 14 years proving results about these levels, including that parts of the game are harder than famous problems like the traveling-salesman problem and factoring large numbers.

The surprise here is what the students proved with the 2023 final project. They used fan-made Super Mario level editors and Super Mario Maker to create levels so hard they are undecidable. In practical terms, the “can Mario reach the castle?” question stops being something computation can always answer. The paper’s argument uses a standard theoretical computer science move called a reduction: convert a problem you want to solve into a problem you already know is hard.

The article’s “pot of boiling water” analogy captures the logic: if you already know how to do a task for a certain kind of problem, then you can translate a new problem into that old one. In this case, the team “broke down” a Super Mario level into localized parts of Mario’s path called gadgets. A gadget, in their sense, is anything in the environment that decides whether Mario can go through a particular pattern. One example is the door gadget. In that gadget, a Spiny is always either on the left or right of a door, so the door’s state is effectively open or closed. Mario’s actions and timing determine whether he can transition the Spiny across the door, which flips the door state.

Once you can make gadgets behave like logic variables, the game becomes a substrate for simulating hard problems. Earlier work had already strung together multiple door gadgets to simulate true-or-false problems that complexity researchers knew were difficult. But for undecidability, this project added more power: it built a counter gadget that tallies monsters and obstacles. Demaine explains that if you can construct even a few counters, you can simulate an arbitrary computer that can essentially do anything a non-quantum computer could do, given enough time and memory. That is where the proof connects back to the classic Halting Problem.

The Halting Problem, introduced by Alan Turing in 1936, is built on a paradox. Imagine an “Oracle” that always correctly determines whether any program will halt. Add a “Contrarian” computer that does the opposite of the Oracle’s prediction, and the Oracle becomes wrong for at least one input. The result is undecidability: no algorithm can solve the classification for all possible programs.

The Super Mario proofs rely on a more complex version of the same idea. Instead of asking whether an arbitrary computer halts, the authors reduce known undecidable behavior to the structure of Mario movement in these specifically crafted levels. That is why the article frames Super Mario as “undecidable” rather than just “unsolvable by current brute force.” In boardroom terms, the difference is existential. PSPACE implies problems may be solvable, just not feasibly with growing input size. RE-Complete implies there is no always-correct algorithm.

For executives and investors watching AI, automation, and systems engineering, this is a useful reminder with zero hype and all consequence: some classes of problems do not just require more compute. They break the guarantee layer itself. If your strategy assumes every question can be mapped to an algorithmic answer, results like this are the natural enemy of that assumption. When the game’s reachability becomes undecidable, it mirrors the hard truth inside software and operations at large: there will always be boundaries where verification stops being a matter of scaling.

None of this changes that companies will keep building algorithms, tooling, and better heuristics. But it should sharpen how decision-makers think about “can we determine the outcome?” versus “can we approximate the outcome fast?” The Mario result, built by four MIT students under Demaine’s guidance and supported by a decade and a half of prior proofs, draws a line that is genuinely fundamental: in certain well-defined worlds, there is no program that always tells you the answer. That is the stake.