Super Mario levels proven mathematically impossible, MIT shows

Scientific American reports that a team of five MIT researchers has proved that some levels in the Super Mario series are mathematically unsolvable. The work, circulated as a preprint in 2024, shows that the question "Can this level be beaten?" belongs to a class of problems for which no general algorithm exists.

To understand what that means, you need to know how computer scientists classify problems. Simple ones, like checking whether two points in a network are connected, scale polynomially with the size of the network. That class is called P. Harder problems, like finding the optimal route through many cities, scale exponentially. Those are in NP. But above both sits a third class: undecidable problems. No finite sequence of steps can solve them for all possible cases.

The most famous undecidable problem is the halting problem, which Alan Turing described in 1937. It asks: given a computer program, will it ever stop running? Turing proved there is no universal algorithm that can answer that question for every program.

The MIT team connected Super Mario to the halting problem using a technique called reduction. They built a simplified model of a counting machine that could be implemented inside the game. The machine's memory was represented by the number of enemy characters. Mario's path through a level was broken into segments, each corresponding to an instruction: add an enemy, remove an enemy, or open a passage when no enemies remained. If the passage opened, the machine had halted.

Under those conditions, asking whether Mario can reach the goal is the same as asking whether the counting machine halts. Since halting is undecidable, so is the solvability of the level. The proof works for several games, including the New Super Mario Bros. series (starting in 2006) and the Super Mario Maker games (2015 onward), according to Scientific American.

One of the paper's authors, Erik Demaine, told New Scientist, "We don't know how to prove that a game is fun. But we can prove that it's hard and that maybe gives some insight into why it's fun." The results cover only specific titles, not the original Super Mario Land that many of us played on long car rides. That classic is not in the undecidable category—which may be a relief to anyone who ever blamed the Game Boy's lack of a save feature for their inability to finish the game.

• computer science
• Erik Demaine
• mathematics
• MIT
• Super Mario
• video games