Here are two facts about mathematics that are often not advertised: 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, conjecture or concept will simply never be solved by anyone, ever. And second, inspiration for high-level math ideas can sometimes come from the most unexpected places.
Case in point: a recent paper currently sitting on the arXiv preprint server (that is, not yet peer-reviewed) by none other than… Super Mario Bros.
“From the 2D Mario games released since then New Super Mario Bros.we have shown that all except for Super Mario Wonder are undecided,” reports the paper, authored by a research team from the MIT Computer Science and Artificial Intelligence Laboratory’s Fortitude Group.
And for Super Mario Wonder“There is evidence to suggest that it may be[,] based on the presence of events and endless 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 intractable problem is, in essence, what it sounds like: it’s a question to which it’s impossible to get a correct yes or no answer. In this case, the problem is one that, as a player, you’d really hope is more straightforward – it’s simply, “Can the game be beaten?”
“You can’t get any harder than that,” Erik Demaine, a professor of computer science at MIT and one of the authors of the paper, told New Scientist. “Can you make it to the bottom? There is no algorithm that can answer this question in a given time.”
Now, trying something like this is no easy task – after all, just playing the game endlessly while the fun use of a research grant is clearly out of the question. So instead, the team used a technique already used a decade ago by MIT graduate student Linus Hamilton for the game. braid.
“The central idea was to represent the value of each counter in a braid level according to the number of enemies occupying a certain location in the level, – the newspaper explains, – “taking advantage of the fact that this number can be arbitrarily large even in a level of limited size.”
In official language, the team was creating a countermeasure machine: a theoretical machine that models how a computer works by manipulating a series of “counters”. They are very simple – a counter inside Super Mario Bros. was only equipped with “up”, “down” and “jump” instructions, nothing more – but incredibly useful, being able to reduce the problem of potentially infinite Goombas to something much easier: the problem of prohibition.
What will she say? Well, start a computer program and hit go – will it ever finish? 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 halting problem – how braid maybe many of them Super Mario Bros. the games – then she too is undecided.
“The idea is that you’ll only be able to solve this Mario level if this particular calculation completes, and we know there’s no way to determine that,” Demaine told New Scientist, “and so there’s no no way to determine if you can solve the level.”
In other words: the next time someone says you’re wasting time playing silly video games, don’t worry—you can instead inform them that you are Actually solving an intractable problem in the field of complexity theory. Goombas and sentient dinosaurs are just window dressing.
The study is posted on arXiv.