On the Turing completeness of Mario - TAS Arbitrary Code Execution
Is Super Mario World turing complete? #
With this TAS (Tool assisted Speedrun) from the Runner "Masterjun" being rather old, and the Title being somewhat clickbaity - lets dive right into the Content itself and let me proof you that this is a rather magnificent achievement. I want to talk about two Speedruns, the first one being from 2013 and the second one from 2014.
The Screen Recording of AGDQ 2014 initially left me completely baffled (see e.g. Screenshot below). So lets wrap our Head around what is going on here and what makes this particular run so special.
Foremost, this run was done on actual Hardware, controlled by a Raspberry Pi used for the Input, which is not the norm for TAS.
Additionally and much more mind bending, the Games input and nothing else is used on the basis of a Stun Glitch to inject arbitrary Code into the Games Memory.
So in more simple Terms, the Games Input is used to reprogram the Memory, more specifically to inject the Code for the Game Pong in this example.
Afterward Pong gets started and is available to be played.
So what about Turing Completeness? #
By definition, any system that can simulate a universal Turing machine is Turing complete. While the Arbitrary Code Execution itself proves that a Turing Machine could theoretically be implemented in Super Mario World, the available memory is the biggest limitation. Not only would this be one of the most impractical implementations of a Turing Machine (which is kind of the whole point of the example), but it would also be quite limited. So, in theory, this TAS-based injection provides Turing completeness for Super Mario World, but the limitations quickly become apparent. But that does not hinder anyone from implementing more Games inside the Game itself.