Now suppose you have another computer, the Contrarian, and you put the Oracle inside it. When you give the Contrarian a program, it passes it to the Oracle and then does the opposite of whatever the Oracle says the program will do. So if the Oracle assesses the Contrarian’s program and thinks it will halt, the Contrarian will run forever. If the Oracle thinks the program will run forever, the Contrarian will halt. Either way, the Oracle’s assessment is wrong, so the classification problem is undecidable.
The proofs that Super Mario is undecidable rely on a more complex version of this idea. The team’s argument breaks down the video game using a technique called a reduction, in which mathematicians convert a problem they’re trying to solve into a problem they already know something about. “The classic example I remember in a math class is: How do you make a pot of boiling water?” Demaine recalls. “Well, I fill up the pot with water from the sink, and then I put it on the stove, and then it eventually boils. Okay, now I’ll give you a pot of water that’s already filled. How do you make a pot of boiling water? Well, I empty out the pot first and reduce to the previous problem.”
In their particular world of platforms and porcupines, the team broke down their Super Mariolevel into localized parts of Mario’s path called gadgets, which they could use to prove that the level was undecidable.
“A gadget in our sense is anything in your environment that decides whether or not you can go through one pattern [within a level],” explains Jayson Lynch ’12, MEng ’15, PhD ’20, a CSAIL research scientist and head of algorithms at MIT FutureTech. For example, in one gadget Mario might need to jump on a platform to avoid a monster as he makes his way across the screen. As a PhD student mentored by Demaine, Lynch spearheaded the formalization of gadget theory and worked on some of the earlier Super Mario papers but did not study the game’s undecidability.
One of Lynch’s favorite Super Mario gadgets is the door gadget, which works like a door that Mario can open, traverse, and close. The door in question is always either open (when the Spiny is on the right) or closed (when the Spiny is on the left). So if a Spiny is pacing back and forth on the left of the door, Mario has to navigate beneath the moving Spiny and jump up to hit a brick block just as the Spiny reaches it. This bumps the Spiny to the right side, which opens the door and allows Mario to travel across the traverse path and get to the spot where he can close the door. Once there, he must time another jump beneath the pacing Spiny to send it back to the left side of the gadget, closing the door behind him.
Since a door is always open or closed, its state can be used to simulate a true or false statement, with open being true and closed being false. Earlier Super Mario papers had strung together multiple door gadgets to simulate a true-or-false problem that complexity researchers already knew to be hard. But to show undecidability, the team used Super Mario level editors to put together another device, called a counter gadget, that tallies the game’s monsters and obstacles.
If you can build a machine with even just a few of those counters, Demaine says, you can simulate an arbitrary computer—one that could essentially do anything a non-quantum computer could do, given enough time and memory. And with no limit on the number of monsters, such a machine could have infinitely expandable memory, even though the level size stays the same, which he calls “pretty wild.” In other words, any theoretical computer can be built in a Super Mario level. “You could use it to solve anything you can use a computer to do,” says Demaine. “You could have it do your taxes, or compile your code, or run an LLM, or optimize your class schedule.” You might even build Super Mario levels that could excel at sudoku, construct optimal chess strategies, or prove any provable mathematical theorem.
#Super #Mario #mathier