Mario Maker Calculator is not Turing-complete
In the video "We Built A Computer in Mario Maker!", the Game Theorists describe a machine made in Mario Maker that uses logic gates to add two numbers from 0-7 and prints the result as a decimal, with inputs encoded as 3-bit numbers. The Game Theorists claim that this machine is Turing-complete.
Mario Maker Calculator can be compiled into Python as this function,
def mariomakercalculator(a, b): print(a % 8 + b % 8)
which can be unshackled as this,
c = 0 def mariomakercalculator(a, b): global c c += a + b print(c)
A Mario Maker Calculator program consists of arbitrarily many mariomakercalculator()
commands.
Computational class
If A (ignoring extensions such as I/O) cannot be compiled into B, then B is of a computational class equal to or lower than that of A. If A is a Turing-machine, then B must strictly be weaker than A.
Problem
If MMC Unshackled is Turing-complete, this Befunge-93 code should be compilable into it.
0>1+:.v ^.:+1<
Solution
The initial 0
is implicit.
The top line can be compiled into MMC Unshackled as mariomakercalculator(0, 1)
. This is also true for the bottom line. Now we have the following.
mariomakercalculator(0, 1) mariomakercalculator(0, 1)
The instruction pointer moved back to the top, and then to the bottom. We can compile this simply by copies our code. Now we have the following.
mariomakercalculator(0, 1) mariomakercalculator(0, 1) mariomakercalculator(0, 1) mariomakercalculator(0, 1)
This also needs to repeat, and what we would have would also need to repeat. Now we have a program with infinitely many commands. Since this algorithm requires infinitely many instructions, this code cannot be compiled into MMC Unshackled.
Conclusion
Therefore, Mario Maker Calculator Unshackled, and by extension Mario Maker Calculator, must be a push-down automaton or weaker. The Game Theorists are wrong.