Researchers from MIT have formally proved that Super Mario Bros. is RE-Complete, the highest complexity class for undecidable problems. That means no computer program can ever reliably determine whether Mario can reach the castle in an arbitrary level. The finding, produced by four students in Erik Demaine's 2023 course Algorithmic Lower Bounds: Fun with Hardness Proofs, overturns Demaine's own prior claim that PSPACE was Super Mario's 'permanent home.'
The proof works through a technique called reduction, converting the Mario completion problem into a known undecidable problem: Alan Turing's 1936 Halting Problem. The students built custom levels using fan-made editors and Super Mario Maker, then decomposed those levels into localized path segments called gadgets. Each gadget models a discrete logical state, like a door controlled by a Spiny's position. String enough gadgets together and you have a system no algorithm can fully evaluate.
What makes this paper worth reading in full is not the conclusion but the mechanics. The gadget framework, formalized by CSAIL research scientist Jayson Lynch, is a general tool applicable far beyond Mario. Demaine's group has spent 14 years proving Mario harder than the traveling-salesman problem and large-number factoring. RE-Complete is the ceiling. The question now is what other games sit there too.
[READ ORIGINAL →]