News for hackers. Stuff that matters.
Re:Surprisingly Turing-Complete by exDM69 on Friday October 02, 2015 @10:44AM (#10318865)
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/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.

Re:Surprisingly Turing-Complete by panic on Friday October 02, 2015 @05:29PM (#10321468)
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.

[1] http://dwarffortresswiki.org/index.php/DF2014:Computing