These Super Mario levels are mathematically unsolvable
NEWS | 08 October 2026
In math and Mario Land, there are questions that are algorithmically undecidable, meaning they will demonstrably never have an answer I agree my information will be processed in accordance with the Scientific American Inc. Privacy Policy . We leverage third party services to both verify and deliver email. By providing your email address, you also consent to having the email address shared with third parties for those purposes. This article is from Proof Positive, our friendly newsletter that explores the joys and peculiarities of math. Sign up today for a weekly math essay and puzzle in your email inbox. During my childhood, I spent a lot of time in the backseat of a car during school holidays as my parents drove my brother and me to visit relatives in France. That meant killing time for eight to 10 hours in the cramped car. So I was thrilled when I got my first Game Boy and the game Super Mario Land to go with it. On supporting science journalism If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today. As the oldest Game Boy game in the Super Mario series, its main difficulty lay in the fact that you couldn’t save your progress and always had to start from the beginning after turning the game off. It took a lot of time and patience to work your way to the final level, defeat the boss and rescue Princess Daisy. I had plenty of that time on long car journeys, and I can say with some pride that Super Mario Land is one of the few games I’ve played through from beginning to end multiple times. But I must admit that on some days the game seemed unsolvable to me, which was definitely because of my lack of skill. So I was surprised when I recently stumbled across a mathematical research preprint from 2024 with the promising title “You Can’t Solve These Super Mario Bros. Levels: Undecidable Mario Games.” In it, five Massachusetts Institute of Technology researchers prove that many newer games in the Super Mario series are mathematically maximally complex and therefore contain unsolvable problems. A branch of theoretical computer science—some might even classify it as mathematics—deals with the complexity of problems. It involves assessing how computationally expensive it is to develop a solution and categorizing problems accordingly. This allows us to determine which tasks are potentially solvable by a computer—or indeed, by any computer at all. An example of a “simple” problem is whether two points in a network are connected. While finding a solution becomes more computationally expensive as the network grows, the number of computational steps will scale at most polynomially with the network size (that is, the network size raised to the power of a constant) and not exponentially (meaning a constant would be raised to the power of the network size). For such problems, experts have introduced the complexity class “P.” But some tasks are significantly more difficult to solve. The effort required increases exponentially with the size of the problem; this is the case, for example, with finding the optimal route when given a series of parameters, as in the mathematical puzzle the traveling salesman problem. Even though such problems are complex, they can be checked for correctness relatively quickly. These types of problems therefore fall into a different problem class, which is called “NP.” And then there are the problems that have no solution, such as, for example, the halting problem: back in 1937, mathematician Alan Turing proved that there can be no algorithm that can universally determine whether a computer program will halt or continue running indefinitely. Such problems are algorithmically unsolvable. A computational procedure with a finite number of steps is insufficient to solve them. And as the experts at M.I.T. demonstrated in 2024, some Super Mario games fall into this unsolvable class. Counting Monsters and Playing Super Mario To prove that a problem belongs to a particular problem class, experts use the principle of reduction. This involves reducing one problem to another. For example, if it can be shown that the solution to a question about a Super Mario game would solve the halting problem, then Super Mario is at least as complex as the halting problem itself. And that’s exactly what the researchers did. They focused on the question of whether a level in a Super Mario game is solvable—meaning that it can, in principle, be solved by trying all finite sequences of inputs—and equated this with the halting problem. The team used a simplified version of the halting problem for this purpose. As it turns out, this problem can be formulated even for very simple computer models, so-called counting machines. These are theoretical models of computers that can only execute a handful of instructions: increase a counter by one, decrease it by one, halt, and, if the counter is zero, jump to another instruction. Even a rudimentary machine with these capabilities leads to the halting problem. As the researchers demonstrated, a counting machine along these lines can be implemented in some games of the Super Mario series. This allows the question of whether the machine will eventually stop to be reframed as: Can the player reach the goal in this level? The researchers encoded a counter value based on the number of enemy characters in the game. First, they theoretically modified the games under consideration so that they had no time limit and the total number of enemies was no longer restricted. The team broke down Mario’s possible path through a level into individual sections, each corresponding to a calculation instruction of the counting machine. For example, the counter is “incremented,” or increased, meaning an enemy spawns when Mario traverses a specific path. This corresponds to the increment function. Other paths, however, decrease the number of enemies (decrement), and still other areas can open a passage when there are no more enemies (jump-if-zero). If, at some point, the path to the goal opens for Mario in this way, the simulated computer model has entered a halt state. To find out if there’s always a way for Mario to reach the goal, one would have to determine whether the corresponding counting machine comes to a halt. Because the halting problem is generally undecidable, however, this also applies to the solvability of a Super Mario level. The team has explicitly applied this proof idea to several Super Mario games, including those in the New Super Mario Bros. series, whose first installment was released in 2006, and the Super Mario Maker games released around 10 years later, in all their variations. “We don’t know how to prove that a game is fun,” one of the authors, Erik Demaine, told New Scientist. “But we can prove that it’s hard and that maybe gives some insight into why it’s fun.” Because Super Mario is maximally complex, it could be one of the most fun games ever by this criterion. For me, that was definitely the case on long car journeys—even if the version of Super Mario that I played is not among the most complex games. This article originally appeared in Spektrum der Wissenschaft and was reproduced with permission. It was translated from the original German version with the assistance of artificial intelligence and reviewed by our editors.
Author: Daisy Yuhas. Manon Bischoff.
Source