Here are two facts about mathematics that often go unadvertised: first, there are some problems that are simply unsolvable. It’s not that you personally aren’t smart enough or that you’re using the wrong method to figure it out; a question, conjecture or concept is simply never solved by anyone. And second, inspiration for high-level mathematical ideas can sometimes come from the most unexpected places.
Case in point: a recent article currently on the arXiv preprint server (meaning it hasn’t been peer-reviewed yet) by none other than… Super Mario Bros.
“Of the 2D Mario Games released since then New Super Mario Bros.we have shown that all but Super Mario Wonder are undecidable,” according to a paper authored by a research team from the MIT Computer Science and Artificial Intelligence Laboratory’s Hardness Group.
Even for Super Mario Wonder“There is evidence to suggest that this may be the case[,] based on the presence of events and endlessly spawning Goombas,” they add, “but the game is still very new and more research is needed to understand the mechanics of the game well enough to make further claims about undecidability.”
So what does this mean in practice? An undecidable problem is basically what it sounds like: it’s a question that cannot be properly answered with a yes or no. In this case, the problem is one that you, as a player, would really hope would be more straightforward – it’s simply, “Can the game be beaten?”
“You can’t get any harder than this,” Erik Demaine, a computer science professor at MIT and one of the paper’s authors, told New Scientist. “Can you reach the finish line? There is no algorithm that can answer this question in finite time.”
Now, proving such a thing is not an easy task – after all, simply playing the game endlessly while having fun using a research grant is obviously out of the question. Instead, the team used a technique already used by MIT student Linus Hamilton for the game a decade ago. Braid.
“The central idea was to represent the value of each counter va Braid level according to the number of enemies occupying a specific location in the level,” the sheet explains, “taking advantage of the fact that this number can be arbitrarily large even in a limited-size level.”
In formal language, the team was building a counter: a theoretical machine that models how a computer works by manipulating a set of “counters”. They are very simple – one counter in Super Mario Bros. it was only equipped with the instructions “up”, “down” and “jump”, nothing more – but incredibly useful, because it managed to reduce the problem of potentially endless Goombas to something much simpler: the problem of stopping.
What does it mean? Well, run a computer program and press “go” – does it ever end? Or just keep running forever? This may sound like a silly question, but this is a halting problem—a classic example of an undecidable problem. If the game can be reduced to a halting problem—as Braid can and many of them Super Mario Bros. games – then it is also undecidable.
“The idea is that you’re only going to be able to solve this Mario level if that particular calculation ends, and we know there’s no way to determine that,” Demaine told New Scientist, “and so there’s no way to determine whether it can solve the level.”
In other words, the next time someone tells you that you’re wasting your time playing stupid video games, don’t worry—you can instead inform them that actually solving an undecidable problem in the field of complexity theory. Goombas and sentient dinosaurs are just decorations.
The study is published on arXiv.