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.