3 ms·

Here's a challenge for you guys: Super Mario Maker. It hasn't been proven Turing complete yet, but I'd be surprised if it wasn't. Here's a pointer for you to g

by exDM69 11y ago

Here's a challenge for you guys: Super Mario Maker. It hasn't been proven Turing complete yet, but I'd be surprised if it wasn't. Here's a pointer for you to get started: http://www.gamefaqs.com/boards/805618-super-mario-maker/72515728 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.

asgard1024 11y ago
My other favorites are Spacechem (https://www.youtube.com/watch?v=EzzLzUCRmBw https://www.youtube.com/watch?v=EzzLzUCRmBw) and Terraria.
- thelucky41 11y ago
  Let's not forget Dwarf Fortress, which has several mechanisms that are accidentally turing complete. My favorite is the logic gate using animal behavior. [1] http://dwarffortresswiki.org/index.php/DF2014:Computing http://dwarffortresswiki.org/index.php/DF2014:Computing
jamesmiller5 11y ago
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 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.
panic 11y ago
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_mario_maker_science_spawning_despawning_and/ 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.
- steveklabnik 11y ago
  This was (is?) a problem in Minecraft as well, when people were first trying to build CPUs in it.

by exDM69 11y ago

asgard1024 11y ago

My other favorites are Spacechem (https://www.youtube.com/watch?v=EzzLzUCRmBw https://www.youtube.com/watch?v=EzzLzUCRmBw) and Terraria.

thelucky41 11y ago
Let's not forget Dwarf Fortress, which has several mechanisms that are accidentally turing complete. My favorite is the logic gate using animal behavior. [1] http://dwarffortresswiki.org/index.php/DF2014:Computing http://dwarffortresswiki.org/index.php/DF2014:Computing

jamesmiller5 11y ago

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

panic 11y ago

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

steveklabnik 11y ago
This was (is?) a problem in Minecraft as well, when people were first trying to build CPUs in it.