Mathematicians discover impossible problem in Super Mario games | Hacker News Reader

Mathematicians discover impossible problem in Super Mario games

newscientist.com

21 pointsRafelMri13 comments

You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games https://arxiv.org/abs/2405.10546

Where can I play these games?

> 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.

> 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.

Such a waste of time. Should have been at most someone's bacherol thesis.

I feel like much of modern number theory has about the same level of usefulness

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.

https://archive.is/1Y7gX

how do computer scientists prove negatives all the time?

A negative is just a reverse of a positive.

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.

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.

"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.

17% funner than the leading competing "fun-time experience"

Something, something, time-dilation neurocatheter

Reply on news.ycombinator.com