MAKE: Blog: LEGO Turing machine

LEGO Turing machine

Turing Top
Turing Middle
Turing Bottom
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.

Related:

Comments

Oldest comments listed first.

Posted by: Josh Hernandez on June 12, 2008 at 1:22 AM

Just one stack?

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

Posted by: on June 12, 2008 at 5:19 AM

looks like a queue

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.

Posted by: The Oracle on June 12, 2008 at 10:41 AM

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.

Subscribe to MAKE Magazine!

Subscribe today, save 42% and get web access to MAKE free. MAKE Digital Edition is available only to subscribers.

$34.95 / 1 year
(4 Quarterly Issues)

Subscribe now

Void your warranty, violate a user agreement, fry a circuit, blow a fuse, poke an eye out... Welcome to the Make Blog!

Features and more @ MAKE!

Get MAKE 14 - Subscribe or on newsstands!

Add MAKE to iGoogle - GoogleGoogle.
Add MAKE to your RSS reader - Real simple.
Add MAKE on Twitter.
Add MAKE on FriendFeed & the MAKE room.

Why advertise on MAKE?
Read what folks are saying about us!

Click here to advertise on MAKE!

Phillip Torrone
Senior Editor
Tel: 707-827-7311

Gareth Branwyn
Robot Maker

Kip Kay
Video Maker

Jonah Brucker-Cohen
Artist / Researcher

Suggest a Site!

Natalie Zee Drieu
Senior Editor
CRAFT

Becky Stern
Culture jammer

Collin Cunningham
Sound Maker

Marc de Vinck
CNC Maker

Current Podcast

Weekend Project: Styrofoam Plate Speaker Get surprisingly good sound from disposable picnicware with this easy to make and inexpensive Styrofoam Plate Speaker. Thanks go to José Pino for the original article in Make Magazine.To download Styrofoam Plate Speaker MP4 click here or subscribe in... More...

Get the Make blog sent via email

Enter your email to receive the Make blog each day:

WOW! Thanks to everyone involved with Maker Faire Bay Area: attendees, makers, exhibitors, sponsors, volunteers, and crew...it was AMAZING! Over 400 Makers and 60,000+ attendees! Be sure to check out the photos @ Flickr, and our Maker Faire posts for all the action! The next scheduled Maker Faire is Austin: Oct. 18th & 19th, 2008 - Travis County Expo Center!