Here are two facts about math that are often not advertised: First, there are some problems that are simply unsolvable. It’s not that you’re personally not smart enough, or that you’re using the wrong method to find out; the question, conjecture or concept will simply never be 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 (that is, not yet peer-reviewed), about none other than… Super Mario Bros.
“From the 2D Mario Games that have been released since New Super Mario Bros.we have shown that everything but Super Mario Wonder are undecidable,” reports the article, written by a research team from the Hardness Group of the MIT Computer Science and Artificial Intelligence Laboratory.
Even before Super Mario Wonder“There are indications that this may be the case[,] based on the presence of events and the infinite spawning of 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 statements about undecidability.”
So what does that mean in practice? An undecidable problem is basically what it sounds like: it’s a question to which it’s impossible to find a correct yes or no answer. In this case, the problem is one that, as a gamer, you would actually hope was easier: it’s very simple: “Can the game be beaten?”
“You can’t get better than this,” Erik Demaine, a professor of computer science at MIT and one of the authors of the paper, told New Scientist. ‘Can you reach the finish line? There is no algorithm that can answer that question in a limited time.”
Now it’s not easy to prove something like that. Simply playing the game ad infinitum, while a fun application for a research grant is apparently out of the question. Instead, the team used a technique already applied to the game by MIT student Linus Hamilton a decade ago Braid.
“The central idea was to represent the value of each counter in a Braid This level is determined by the number of enemies occupying a given location in the level,” the paper explains, “exploiting the fact that this number can be arbitrarily large even on a level with a limited size.”
In formal terms, the team was setting up a counting machine: a theoretical machine that models how a computer works by manipulating a series of ‘counters’. They are very simple: one counter-in Super Mario Bros. was only equipped with ‘up’, ‘down’ and ‘jump’ instructions, nothing more – but incredibly useful, as it was able to reduce the problem of potentially infinite Goombas to something much simpler: the stopping problem.
What does that mean? Well, start a computer program and press “go” – will it ever end? Or just keep running forever? It may sound like a silly question, but this is the stopping problem – a classic example of an undecidable problem. If a game can be reduced to the stopping problem – like Braid can, and so much of the Super Mario Bros. games – even then it is undecidable.
“The idea is that you can only solve this Mario level if this particular calculation is terminated, and we know 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, the next time someone says you’re wasting time playing stupid video games, don’t worry. Instead, you can let him or her know that you Actually solving an undecidable problem in the field of complexity theory. The Goombas and sentient dinosaurs are just window dressing.
The research has been posted on arXiv.