One big limitation in Super Mario Maker is that objects too far horizontally offscreen are not simulated and may "de-spawn". Here's a more detailed description of the rules: https://www.reddit.com/r/MarioMaker/comments/3lcrqb/super_ma...
This means you have to include Mario's position in your design if the device is larger than the horizontal simulation area. Just chaining together NAND gates isn't necessarily enough.
Re:Surprisingly Turing-Complete
by steveklabnik on Friday October 02, 2015 @06:22PM
(#10321700)
This was (is?) a problem in Minecraft as well, when people were first trying to build CPUs in it.
Re:Surprisingly Turing-Complete
by jamesmiller5 on Friday October 02, 2015 @01:58PM
(#10320142)
If you didn't catch it in the article, it links to a proof of Braid the game's undecidability without use of it's time mechanics.
http://arxiv.org/abs/1412.0784
I'd guess Super Mario Maker could be similar if monsters can infinitely spawn, be destroyed and interact with one another, skimming the paper it looks like a requirement.
Re:Surprisingly Turing-Complete
by asgard1024 on Friday October 02, 2015 @11:22AM
(#10319101)
My other favorites are Spacechem (https://www.youtube.com/watch?v=EzzLzUCRmBw) and Terraria.
Re:Surprisingly Turing-Complete
by thelucky41 on Friday October 02, 2015 @06:14PM
(#10321662)
Let's not forget Dwarf Fortress, which has several mechanisms that are accidentally turing complete. My favorite is the logic gate using animal behavior.
Here's a pointer for you to get started: http://www.gamefaqs.com/boards/805618-super-mario-maker/7251...
This guy says he has built a single nand gate, but hasn't been able to connect several together.
As a gamer and a computer scientist, I find Turing complete games intriguing. Minecraft's Redstone is probably intentionally Turing complete, but for example the signalling of trains in OpenTTD probably is not.