LEGO Turing machine

Here’s a great LEGO based Turing machine, Denis writes -

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.

I programmed a small interface (through an Access database so Microsoft Access must be installed on your computer) to enter an test simple Automaton With Append (AWA or AAA in French). Follow this link to download the demo: AAA.zip.

One reason to build the automaton with append instead of the original Turing machine was that I avoided building a bi directional (near) infinite tape.

3 Responses to LEGO Turing machine

Josh Hernandez on June 12th, 2008 at 1:22 am said:

I thought an FSM needed two stacks to be equivalent to a Turing Machine, unless it has random access to the stack’s contents (I haven’t looked too deeply into this project, so maybe it’s explained inside).

Reply ↓
Anonymous on June 12th, 2008 at 5:19 am said:

Ya without random access this is a push down automaton, needs 2 to be a turing machine. But I think that this is actually using a queue. It looks like the reading is done at the bottom. A single queue would be enough to simulate a turing machine. It does seem confusing though. The example AxnBxn is also a bit confusing because it’s a classic context free problem, so you don’t need a full turing machine, just a push down automaton.

Still cool though.

Reply ↓
The Oracle on June 12th, 2008 at 10:41 am said:

You’re right that with a stack, it’s a push-down automaton.

But if you want to get techincal, without an infinite stack, it’s computationally equivalent to a finite state machine.

Reply ↓