The seemingly simple question below has a mathematical answer that will blow your mind. Think of any 2D Super Mario game. Now, would you say that you can beat all of these titles? If your answer is yes, experts have come to inform you that you, in fact, can't. At MIT, scientists found a mathematically impossible formula in the games of Nintendo’s most famous plumber.
Undecidable games. The paper, published as a pre-print on arXiv by a team from MIT’s Computer Science and Artificial Intelligence Laboratory, found that 2D Super Mario games released since New Super Mario Bros. are all undecidable. The one exception is the latest title, Super Mario Wonder (simply because it’s new and needs more study, the study's authors explain).
In practice—and mathematical terms—an undecidable problem means that the problem has no solution. In other words, it’s a question for which it’s impossible to find a correct "yes" or "no" answer. In this case, and as video game players, we’d really expect it to be easier. But it isn’t.
An impossible Super Mario game. As the MIT researchers explain in the paper, there’s nothing more complex than an undecidable problem: “Can you get to the finish? There is no algorithm that can answer this question in a finite amount of time,” Erik Demaine, an MIT computer science professor and one of the study's authors, told NewScientist.
But it’s not easy to prove what the researchers are saying. As such, how did they arrive at their conclusion?
Computational complexity. The authors based their work on studying how difficult and slow it is to solve various problems algorithmically. They started with an advantage: Previous studies showed that determining whether it’s possible to complete certain levels in Super Mario games is a task that belongs to a group of problems known as NP-hard, where complexity grows exponentially.
Complexity is extremely difficult to calculate for all but the most minor problems. However, MIT researchers added an extra twist by demonstrating that answering this question isn’t only difficult, but impossible for certain levels of Super Mario games.
The “trick” to an impossible Super Mario game. Although it may seem contradictory—(how can you not finish a Super Mario game?)— a computer can't solve undecidable problems, no matter how powerful or long you let it run. However, MIT researchers admit to a little “trick” to make them fit in as “undecidable.” First, the researchers analyzed custom levels that allowed them to place hundreds or thousands of enemies in a single location.
How? By removing the limits game producers impose on the number of enemies at a level. In addition, they used the location of enemies within the level to create an abstract mathematical tool called a “counter machine,” creating a functional computer within the game. This way, they gave the Super Mario counter straightforward instructions: “up,” “down,” and “jump.”
The halting problem. With the “trick” done, the MIT experts used a concept called the “halting problem,” another mathematical enigma that states that, in general, there’s no way to determine whether a given computer program will ever terminate or run forever, other than to run it and see what happens.
Thus, the research team showed that no analysis of the game level can say for sure whether it will ever be able to finish or not. “The idea is that you can only solve this Mario level if this particular computation finishes, and we know there’s no way to determine that, so there’s no way to determine if you can solve the level,” Demaine concludes.
Image | Nintendo
Related | Nintendo Switch 2: News, Rumored Release Date, Price and Everything We Know So Far
View 0 comments