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; the question, assumption, or concept will simply never be resolved by anyone, ever. And second, inspiration for high-level mathematical ideas can sometimes come from the most unexpected places.
Case in point: a recent paper currently on the arXiv preprint server (that is, not yet peer-reviewed) concerning none other than… Super Mario Bros.
“From the 2D Mario Games released since then New Super Mario Bros.we have shown that all except Super Mario Miracle are intractable,” reports the paper, compiled by a research team from the Hardness Group of MIT’s Laboratory for Computer Science and Artificial Intelligence.
Even for Super Mario Miracle“there is evidence to suggest that this may be the case[,] based on the presence of events and infinite spawning of Goombas,” they add, “but the game is still very new and more research is needed to understand the game mechanics well enough to make further claims about undecidability.”
So what does this mean in practice? An insoluble problem, in essence, is what it sounds like: it is a question for which it is impossible to find a correct yes or no answer. In this case, the problem is one that as a gamer you really hope is clearer – it’s quite simply “Can the game be beaten?”
“You can’t get any harder than that,” Eric Demain, a professor of computer science at MIT and one of the paper’s authors, told New Scientist. “Can you make it to the finish line? There is no algorithm that can answer this question in a finite amount of time.
Now, proving something like this is no easy task – after all, just playing the game ad infinitum, while fun using a research grant, is clearly out of the question. So instead, the team used a technique already used a decade ago by MIT student Linus Hamilton for the game Braid.
“The basic idea was to represent the value of each counter in a Braid level by the number of enemies occupying a certain location in the level,” the paper explains, “taking advantage of the fact that this number can be arbitrarily large even in a limited-sized level.”
In formal language, the team was building a counter machine: a theoretical machine that models how a computer works by manipulating a set of “counters”. They are very simple – one counter Super Mario Bros. was only provided with the instructions “up”, “down” and “jump”, nothing more – but incredibly useful, able to reduce the problem of potentially infinite Goombas to something much simpler: the problem of stopping.
What does this mean? Well, start a computer program and hit ‘go’ – will it ever quit? Or just keep running forever? It may sound like a silly question, but this is the halting problem—a classic example of an intractable problem. If a game can be reduced to the problem of stopping – as Braid can, and so many of Super Mario Bros. games – then this is also undecidable.
“The idea is that you’ll only be able to solve this level of Mario if that particular calculation is finished, and we know there’s no way to determine that,” Demain told New Scientist, “and so there’s no way to determine whether it can to solve the level.
In other words: the next time someone says you’re wasting your time playing stupid video games, don’t worry—you can instead inform them that you’re in fact solving an intractable problem in the field of complexity theory. Goombas and sentient dinosaurs are just hype.
The study is published on arXiv.
