Here are two facts about math that often go unadvertised: firstly, 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; the question, or conjecture, or concept will simply never be solved by anyone, ever. And secondly, inspiration for high-level math ideas can sometimes come from the most unexpected places.
Case in point: a recent paper, currently residing on the arXiv preprint server (that is to say, not yet peer-reviewed), concerning none other than… Super Mario Bros.
“Of the 2D Mario Games released since New Super Mario Bros., we have shown that all except for Super Mario Wonder are undecidable,” reports the 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 which suggests that it might be[,] based on the presence of events and infinitely 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 that mean, in practice? An undecidable problem, basically, is what it sounds like: it’s a question for which it is impossible to correctly find a yes or no answer. In this case, the problem is one that, as a gamer, you’d really hope was more straightforward – it is, quite simply, “Can the game be beaten?”
“You can’t get any harder than this,” Erik Demaine, professor of computer science at MIT and one of the authors of the paper, told New Scientist. “Can you get to the finish? There is no algorithm that can answer that question in a finite amount of time.”
Now, proving something like that is no easy task – after all, simply playing the game ad infinitum, while a fun use of a research grant, is evidently out of the question. So, instead, the team used a technique already employed a decade ago by MIT grad student Linus Hamilton for the game Braid.
“The central idea was to represent the value of each counter in a Braid level by the number of enemies occupying a particular location in the level,” the paper explains, “exploiting that this number can be arbitrarily large even in a bounded-size level.”
In formal language, the team was setting up a counter machine: a theoretical machine that models how a computer works by manipulating a set of “counters”. They’re very simple – one counter in Super Mario Bros. was equipped only with “up”, “down”, and “jump” instructions, nothing more – but incredibly useful, being able to reduce the problem of potentially infinite Goombas into something much easier: the halting problem.
What does that mean? Well, start up a computer program and press “go” – will it ever terminate? Or just continue running forever? It may sound like a silly question, but this is the halting problem – a classic example of an undecidable problem. If a game can be reduced to the halting problem – as Braid can, and so many of the Super Mario Bros. games – then it, too, is undecidable.
“The idea is that you’ll be able to solve this Mario level only if this particular computation will terminate, and we know that there’s no way to determine that,” Demaine told New Scientist, “and so there’s no way to determine whether you can solve the level.”
In other words: next time someone says you’re wasting time playing silly video games, don’t worry – you can instead inform them you’re actually resolving an undecidable problem in the field of complexity theory. The Goombas and sentient dinosaurs are just window-dressing.
The study is posted to arXiv.
Dr. Sarah Adams is a scientist and science communicator who makes complex topics accessible to all. Her articles explore breakthroughs in various scientific disciplines, from space exploration to cutting-edge research.
