Cynical-C Blog: Lego Turing machine

"I chose to implement in Lego a slightly different version of the original Turing machine. Instead of having a bi directional tape, it uses a stack. When the symbol beneath the stack is read (and removed), the machine changes 'states' and can add zero, one or two symbols on top of the stack.

This variation is maybe very different yet it is possible to show that this simple machine has the same capabilities than a Turing machine. Among other things, it can emulate a Turing machine placed on the stack."
--