The Mario Turing Machine: Why a Video Game Level Can Be Mathematically Undecidable

Think of a classic 2D platforming level. Mario stands on the left edge of the screen; the flagpole is on the far right. Between them sits a configuration of brick blocks, moving platforms, and Koopa Troopas. If you are handed the layout of this level, can you write a computer program that will look at the map and definitively output "yes" if the level is beatable, and "no" if it is not?

The answer is no. And it is not a matter of waiting for faster supercomputers or more sophisticated search heuristics.

In a paper presented at the 2024 International Conference on Fun with Algorithms, a research group including computer scientist Erik Demaine of the Massachusetts Institute of Technology proved that determining whether certain levels in Super Mario Bros. can be completed is algorithmically undecidable. This means the question belongs to the same class of mathematical impossibilities as Alan Turing’s famous halting problem. No algorithm can ever exist that solves this question for every possible Mario level in a finite amount of time.

To understand how a plumber jumping on turtles can bypass the limits of computability, it helps to look at what actually happens when we run a computer program.

Building a Computer Out of Enemies

In 1936, Alan Turing proved that you cannot write a master program that looks at any other computer program and its input and determines whether that program will eventually finish running (halt) or get stuck in an infinite loop.

If you can translate a computer program into a physical system—such that the system reaching a specific state is equivalent to the program halting—then predicting the behavior of that physical system also becomes mathematically undecidable. This is known as "Turing completeness."

To turn a video game into a general-purpose computer, researchers must build the basic components of computation out of the game's native elements. They need logic gates (like AND, OR, and NOT) and a memory storage system.

In the Super Mario Bros. proof, the researchers built what is known as a counter machine. First conceptualized by mathematician Marvin Minsky, a counter machine is a simple model of computation that uses a set of registers, or "counters," that can hold any non-negative integer. The machine can perform only a few basic operations: add one to a counter, subtract one from a counter, and branch to a different instruction if a counter is equal to zero. If you have at least three counters, this minimalist machine is fully Turing-complete.

To represent these numerical counters inside Super Mario Bros., Demaine's team built on a technique pioneered by Linus Hamilton in 2014 for the puzzle game Braid. Instead of using silicon transistors to hold numbers, they used stacks of enemies. The value of a mathematical counter is represented by the physical number of enemies occupying a single, enclosed location in the level.

To increase the counter, the level design forces Mario to trigger a mechanism that spawns another enemy into the pile. To decrease the counter and test if it is zero, Mario must navigate through a sensory "gadget" where enemies are released one by one. If an enemy is present, it blocks Mario's progress or triggers a switch, forcing him down one path (the "subtract" branch). If no enemies remain in the pile, Mario can pass freely (the "zero" branch).

By arranging these enemy-counting gadgets throughout a level, the researchers built a physical architecture that executes the step-by-step logic of a Turing-complete program.

The Problem of Infinite Space

For a system to be truly undecidable, it must have access to infinite memory. In a computer, this would be an infinite tape; in Super Mario Bros., it requires the ability to store an arbitrarily large number of enemies in a counter without the game crashing or forgetting they exist.

This is where the specific physics of individual game engines come into play. Standard hardware limits often prevent too many active sprites from appearing on screen at once. However, the researchers bypassed these limitations by utilizing the underlying code of modern releases like New Super Mario Bros. and Super Mario Maker.

In Super Mario Maker, for example, objects that are off-screen are typically frozen or unloaded to save memory. However, the researchers exploited the game's "global ground" property. Certain platforms and elements remain active even when Mario moves far away from them, allowing the game engine to continuously track and remember the positions of massive piles of off-screen enemies.

By removing the standard level timer—or expanding it exponentially—the level can run its computational processes indefinitely. Mario acts as the instruction pointer, physically running back and forth through the level's logic gates, pulling levers, and releasing enemies to progress the "program." The flagpole at the end of the level is placed behind a door that only opens if the simulated counter machine successfully reaches its "halt" instruction.

Because deciding if the counter machine halts is mathematically impossible, deciding if Mario can ever touch that flagpole is likewise impossible.

The Limit of What Can Be Known

When we play a standard, commercial level of Super Mario Bros., we are not encountering these undecidable monstrosities. Normal levels are built with strict spatial limits and tight timers that force a resolution within a few hundred seconds. Under those constraints, the game is decidable.

But the mathematical proof reveals something fundamental about the systems we design for play. When developers build rich, interactive worlds with consistent rules, they are not just creating environments for entertainment. They are accidentally constructing fully realized computational engines.

If you give players the tools to manipulate state, store information, and branch pathways based on environmental cues, you have given them a computer. And once a system is complex enough to compute, it is complex enough to slip past the boundaries of what mathematics can ever predict.

---

This article is AI-generated (synthetic) content, produced by an automated editorial system with human direction and review. Every claim is traced to published, peer-reviewed sources.