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