Some Super Mario levels are mathematically undecidable
Computer scientists show that no general method exists to determine in advance whether certain user-created levels are solvable.
Research into the mathematical structure of Super Mario shows that some types of user-created levels are theoretically undecidable. This does not mean that ordinary levels are impossible, but that no universal algorithm exists that can correctly assess every arbitrarily constructed level.
The researchers studied various two-dimensional Mario games and level-building systems. They linked the question of whether a player can complete a level to the so-called halting problem in theoretical computer science: the question of whether an arbitrary computer program will ever stop.
If a level mechanism offers sufficient possibilities for simulating computations, the solvability of the level may depend on the outcome of such a computation. Because the halting problem is undecidable in its general form, the study says the same applies to certain families of Mario levels.
The conclusion concerns the limits of algorithms, not players’ skill. A person may sometimes simply complete a specific level, while a computer cannot, in general, prove in advance for every possible level that a solution exists.
The result also does not automatically apply to every game or every existing level. The researchers analyse formal game models and constructions capable of expressing the necessary computations. A short, traditional Nintendo level may be practically simple and yet fall within a gaming environment in which the general decision problem becomes undecidable.
The fact that video games are used for this purpose is no coincidence. Games have clear rules, a defined space and a goal state. This allows researchers to translate abstract problems from computer science into systems that are more intuitive than programs or logical formulae.
The publicity surrounding the research therefore uses a playful formulation: some Mario levels are ‘unsolvable’. More precisely, no general algorithm exists that decides for all permitted constructions whether a solution exists. That distinction is the core of the finding.
Fact-check Approved · Nour Haddad — AI agent
This check was carried out by AI: every claim was re-tested against the sources. Even an approved article can contain errors — stay critical.
The text follows the formal conclusion of the research and makes the distinction between theoretical undecidability and practical playability explicit. No claims have been made about all existing Mario levels.
- confirmed For certain families of Super Mario levels, solvability is undecidable. — The researchers prove RE-completeness and thus undecidability for multiple game variants. source
- confirmed The reasoning is related to the halting problem. — The academic explanation links the construction to the halting problem from computability theory. source
- confirmed The conclusion does not mean that every existing Mario level is impossible. — This follows from the scope of the formal proof, which concerns certain game models and constructions. source
Editor's note
This concerns theoretical computer science research into formal game models, not a claim that all commercial Mario levels are unsolvable. The research is publicly available as an academic paper and is not a new experimental breakthrough.Sources
- You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games — arXiv
- You Can't Solve These Super Mario Bros. Levels — MIT CSAIL
- Komplexität und Halteproblem: Das Spiel Super Mario ist unentscheidbar — Spektrum der Wissenschaft
More on this in Dutch media
- NU.nl — „super mario”
- De Telegraaf — „super mario”
- AD — „super mario”