> We prove RE-completeness (and thus undecidability) of [generalizations of] several 2D games in the Super Mario Bros. platform video game series. These results hold even when we restrict to constant-size levels and screens, but they do require generalizing to allow arbitrarily many enemies at each location and onscreen, as well as allowing for exponentially large (or no) timer. Our New Super Mario Bros. constructions fit within one standard screen size. In our Super Mario Maker reductions, we work within the standard screen size and use the property that the game engine remembers offscreen objects that are global because they are supported by "global ground". To prove these Mario results, we build a new theory of counter gadgets in the motion-planning-through-gadgets framework, and provide a suite of simple gadgets for which reachability is RE-complete.
Yes, TFA headline is intentionally misleading to make the result seem more interesting.
"We don’t know how to prove that a game is fun, we don’t know what that means mathematically"
Sometimes the jokes write themselves :) But seriously, thank goodness for that. I don't want to see the products that come out of the corporations that would be extracting maximum mathematically-proven fun for their widget subscription services.
Right. Proving a negative in the rhetorical or philosophical sense is not the same as proving a negative in the mathematical sense when the mathematical statement has an exact inverse.
You can't prove God doesn't exist. You can only prove he does given the right evidence, but lack of evidence doesn't prove non-existence. This is why Bayesian reasoning has been in use for a long time in science. It moves past the proof obsession to discussing likelihood.
I don't doubt there's pointless research in NT. However, I feel like I should justify just how useless this result is:
In theoretical CS, one is typically interested in the computational complexity of mathematical problems. Early on, researchers identified classes of problems with varying difficulty, as well as certain fundamental problems that appear in many applications. Research in these topics is typically quite interesting.
Studying stupid problems like Super Mario has no merit at all. It probably contains fundamental problems as sub-problems, so the research then just reduces to finding these problems. "Oh look, if I make a level like this it turns into the halting problem, it means Super Mario is undecidable!"
Literally the only reason this is news is because SM is a famous game.
I should confess I didn't read the paper, so I'm just guessing what's going on. However, if there was anything actually interesting going on, there would be more fundamental problems discussed rather than SM.
Edit: read the article, it reduces to halting problem. God damn it.
> To do this they had to remove the limits placed by the game publishers on the number of enemies that can be present in a level.
So they discovered what they intentionally introduced via breakage? It seems they couldn't find what they set out to for, and rather than writing that they just shoe horned the result they wanted into the game.
13 comments
[ 3.1 ms ] story [ 41.6 ms ] thread> We prove RE-completeness (and thus undecidability) of [generalizations of] several 2D games in the Super Mario Bros. platform video game series. These results hold even when we restrict to constant-size levels and screens, but they do require generalizing to allow arbitrarily many enemies at each location and onscreen, as well as allowing for exponentially large (or no) timer. Our New Super Mario Bros. constructions fit within one standard screen size. In our Super Mario Maker reductions, we work within the standard screen size and use the property that the game engine remembers offscreen objects that are global because they are supported by "global ground". To prove these Mario results, we build a new theory of counter gadgets in the motion-planning-through-gadgets framework, and provide a suite of simple gadgets for which reachability is RE-complete.
Yes, TFA headline is intentionally misleading to make the result seem more interesting.
Sometimes the jokes write themselves :) But seriously, thank goodness for that. I don't want to see the products that come out of the corporations that would be extracting maximum mathematically-proven fun for their widget subscription services.
In this case, proving (infinite) A is greater than (finite) B is the same as proving A is not less than B. Tada, negative proved.
You can't prove God doesn't exist. You can only prove he does given the right evidence, but lack of evidence doesn't prove non-existence. This is why Bayesian reasoning has been in use for a long time in science. It moves past the proof obsession to discussing likelihood.
In theoretical CS, one is typically interested in the computational complexity of mathematical problems. Early on, researchers identified classes of problems with varying difficulty, as well as certain fundamental problems that appear in many applications. Research in these topics is typically quite interesting.
Studying stupid problems like Super Mario has no merit at all. It probably contains fundamental problems as sub-problems, so the research then just reduces to finding these problems. "Oh look, if I make a level like this it turns into the halting problem, it means Super Mario is undecidable!"
Literally the only reason this is news is because SM is a famous game.
I should confess I didn't read the paper, so I'm just guessing what's going on. However, if there was anything actually interesting going on, there would be more fundamental problems discussed rather than SM.
Edit: read the article, it reduces to halting problem. God damn it.
So they discovered what they intentionally introduced via breakage? It seems they couldn't find what they set out to for, and rather than writing that they just shoe horned the result they wanted into the game.