Here’s a problem you probably didn’t solve in school: You’re an ambitious young plumber from Brooklyn in a world inhabited by violent human-size mushrooms called Goombas.
Here’s a problem you probably didn’t solve in school: You’re an ambitious young plumber from Brooklyn in a world inhabited by violent human-size mushrooms called Goombas. The love of your life has been kidnapped, so you embark on a quest to rescue her, venturing through stretches of pipe-filled and monster-ridden terrain where your only means of protection are your powers of jumping and stomping.
It’s a journey so arduous that no computer—real or hypothetical—is powerful enough to figure out if you can reach her. And according to research published by the MIT Hardness Group, determining whether your quest is possible at all is at least as complicated as decoding the encryption behind financial transactions. But if this problem could talk, the first thing it would say is “Hello, it’s a-me, Mario!”
Though it does have a YouTube channel, the MIT Hardness Group isn’t an official research group. Instead, it’s a placeholder name for theoretical computer science projects—including several related to Super Mario—from Erik Demaine’s class Algorithmic Lower Bounds: Fun with Hardness Proofs.
Demaine, a professor of computer science, received a MacArthur fellowship (also known as a “genius” grant) for his work in computational geometry on protein folding and origami. But he also researches complexity theory, which focuses on organizing problems into categories based on how much time and memory space it takes for computers to solve them.
He happens to be an avid Super Mario fan as well. “I grew up playing NES [Nintendo Entertainment System] games,” Demaine says. “I poured many hours into playing as a kid, so it’s fun to come back to it these many years later and tie it into my research.”
Super Mario takes place on a horizontally scrolling universe of platforms, pipes, and other obstacles. The object of the game is to rescue Princess Peach, the monarch of the Mushroom Kingdom, by racing through this terrain while sidestepping or dueling monsters like Goombas and deadly porcupines called Spinies. The game takes place over several levels; in the original version, each level ends with a flagpole that sends Mario on to the next part of his mission.
Over the last 14 years, Demaine and his collaborators have proved many things about Super Mario, such as that it’s even harder than the infamous traveling-salesman problem (which seeks the most efficient route between many different locations) or the problem of factoring large numbers. But the result that surprised Demaine the most came from four of his students: Hayashi Ani ’21, MEng ’23; Holden Hall ’26; Ricardo Ruiz ’24, MEng ’25; and Naveen Venkat ’23, MEng ’24. For their final project in that 2023 class, the team used a combination of fan-made Super Mario level editors and a platform called Super Mario Maker to create levels so hard that they are undecidable. In other words, it’s impossible to write a computer program that always correctly predicts whether, in those levels, Mario can reach the castle.
Previously, Demaine had believed that Super Mario belonged in the PSPACE complexity class, which contains problems that are solvable but whose solutions become impractically complex as the problem gets bigger. At the time, he had even said that PSPACE was Mario’s “permanent home.” But the new findings pushed Super Mariointo RE-Complete, the class of undecidable problems. “It’s the hardest complexity class we could imagine for these sorts of games,” Demaine says.
In 1936, Alan Turing, the father of modern computer science,created a puzzle now known as the Halting Problem to prove it’s not possible to construct a computer that can solve everything .
At the core of the Halting Problem lies a paradox, and it goes like this: Suppose you have a fancy computer, called the Oracle, that looks at any program and correctly determines whether a computer following it will ever come to a stop. For example, if it sees the program “Take 1 and add 3,” the Oracle will say the program halts, but if the program says “Take 1 and add 1 to it until it becomes 0,” the Oracle will say it runs forever.
Now suppose you have another computer, the Contrarian, and you put the Oracle inside it. When you give the Contrarian a program, it passes it to the Oracle and then does the opposite of whatever the Oracle says the program will do. So if the Oracle assesses the Contrarian’s program and thinks it will halt, the Contrarian will run forever. If the Oracle thinks the program will run forever, the Contrarian will halt. Either way, the Oracle’s assessment is wrong, so the classification problem is undecidable.
The proofs that Super Mario is undecidable rely on a more complex version of this idea. The team’s argument breaks down the video game using a technique called a reduction, in which mathematicians convert a problem they’re trying to solve into a problem they already know something about. “The classic example I remember in a math class is: How do you make a pot of boiling water?” Demaine recalls. “Well, I fill up the pot with water from the sink, and then I put it on the stove, and then it eventually boils. Okay, now I’ll give you a pot of water that’s already filled. How do you make a pot of boiling water? Well, I empty out the pot first and reduce to the previous problem.”
In their particular world of platforms and porcupines, the team broke down their Super Mariolevel into localized parts of Mario’s path called gadgets, which they could use to prove that the level was undecidable.
“A gadget in our sense is anything in your environment that decides whether or not you can go through one pattern [within a level],” explains Jayson Lynch ’12, MEng ’15, PhD ’20, a CSAIL research scientist and head of algorithms at MIT FutureTech. For example, in one gadget Mario might need to jump on a platform to avoid a monster as he makes his way across the screen. As a PhD student mentored by Demaine, Lynch spearheaded the formalization of gadget theory and worked on some of the earlier Super Mario papers but did not study the game’s undecidability.
One of Lynch’s favorite Super Mario gadgets is the door gadget, which works like a door that Mario can open, traverse, and close. The door in question is always either open (when the Spiny is on the right) or closed (when the Spiny is on the left). So if a Spiny is pacing back and forth on the left of the door, Mario has to navigate beneath the moving Spiny and jump up to hit a brick block just as the Spiny reaches it. This bumps the Spiny to the right side, which opens the door and allows Mario to travel across the traverse path and get to the spot where he can close the door. Once there, he must time another jump beneath the pacing Spiny to send it back to the left side of the gadget, closing the door behind him.
Since a door is always open or closed, its state can be used to simulate a true or false statement, with open being true and closed being false. Earlier Super Mario papers had strung together multiple door gadgets to simulate a true-or-false problem that complexity researchers already knew to be hard. But to show undecidability, the team used Super Mario level editors to put together another device, called a counter gadget, that tallies the game’s monsters and obstacles.
If you can build a machine with even just a few of those counters, Demaine says, you can simulate an arbitrary computer—one that could essentially do anything a non-quantum computer could do, given enough time and memory. And with no limit on the number of monsters, such a machine could have infinitely expandable memory, even though the level size stays the same, which he calls “pretty wild.” In other words, any theoretical computer can be built in a Super Mario level. “You could use it to solve anything you can use a computer to do,” says Demaine. “You could have it do your taxes, or compile your code, or run an LLM, or optimize your class schedule.” You might even build Super Mario levels that could excel at sudoku, construct optimal chess strategies, or prove any provable mathematical theorem.
The MIT mathematician Marvin Minsky invented counter machines in 1961 to figure out how simple a computer could be while still being “universal” (as powerful as any other computer, given enough time). These theoretical computers each store two numbers and can change them by adding 1, subtracting 1, or doing something special if a number hits a set value.
In the counter gadgets the students designed for Super Mario, the numbers reflect how many Goombas the levels contain. A number increases when a pipe spits out a Goomba and decreases when Mario stomps on one. Mario dies if he collides with a Goomba without stomping on it, so he can continue along the path only when the counter is at 0.
Minsky had already proved that counter machines are undecidable because they can run undecidable problems. Since the researchers proved that counter gadgets simulate counter machines, then any level of Super Mario containing a counter gadget will also be unsolvable. “In the future, if someone wants to show a game is undecidable,” explains Holden Hall, one of the students behind the project, “they just have to make one of these gadgets.”
The existence of undecidable problems like the Halting Problem implies that it’s possible to construct an undecidable Super Mario level. Just as the singular undecidable program for the Halting Problem meant thatit’s impossible to figure out if a computer program will run forever, the team’s undecidable level means that it is impossible to determine whether an arbitrary Mario level can be beaten.
More than two years after Demaine’s class on hardness proofs, some of his students continue to meet weekly to discuss their Super Marioresearch.
“From the point of view of complexity theory, studying video games is interesting mostly for didactical reasons,” Fabrizio Grandoni, a research professor at the University of Applied Sciences and Arts of Southern Switzerland, told MIT News in 2016. “It’s a simple, natural way to attract students to study this specific topic.”
Hall, who had very little exposure to the ideas of complexity theory before taking Demaine’s class, is a case in point, noting: “I took the class because a bunch of people I knew were taking it. But since I took it, I really enjoyed the class, and so I’ve taken a lot more classes in that realm.”
The applications of the MIT Hardness Group’s work go way beyond stomping on mushrooms and collecting coins. For example, researchers at the University of Texas Rio Grande Valley (including Timothy Gomez, now a PhD student at MIT) have used the gadget theory developed for analyzing games like Super Marioto study the complexity of problems relating to planning robotic motion and modeling chemical reaction networks.
“[Gadget theory] can be used in the negative way to say ‘Oh, well, we should stop searching for algorithms because we know this problem is too hard’—or it can be used in this positive way, because usually, to prove something hard, you’re showing that you can build a computer of a certain type,” Demaine says.
Though there’s no way of knowing what mark Super Mariowill leave on the future of math and computer science, one thing’s for sure: No matter how many princesses he does or doesn’t save, the legacy of this little plumber is set to extend far beyond video screens.
