We prove RE-completeness (and thus undecidability) of several 2D games in the
Super Mario Bros. platform video game series: the New Super Mario Bros.
series (original, Wii, U, and 2), and both Super Mario Maker games in all five
game styles (Super Mario Bros. 1 and 3, Super Mario World, New Super Mario
Bros. U, and Super Mario 3D World). 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.
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.