The LEGO Turing Machine

A TV Shop themed demonstration of a Turing Machine made in LEGO Mindstorms. It was made as part of a project at computer science at Aarhus University.
A blog about the project is available at http://legoofdoom.blogspot.com

Category:

Science & Technology

Tags:

• Turing Machine
• LEGO
• Mindstorms
• Aarhus University
• palindrome
• binary
• computer science
• Alan Turing
• Turing
• Machine
• robot
• NXT
• project
• computation
• computability
• embedded systems
• embodied agents
• tape
• bricks
• read
• write
• head
• addition
• LEGO!

[mmtrebuchet]

So I was teaching a workshop on computers to middle schoolers not too long ago. Nobody was looking forward to my theory lecture. Then I showed this video, and everyone was suddenly excited about Turing machines. It's a really cool video, and demonstrates the inherent limitations (and lack thereof) of a TM better than just about any other description out there. Plus it's exciting, and the music is awesome!

Thanks,

MMTrebuchet.

[andnissen]

Thank you for your comment. It's really nice to hear that people find our silly video entertaining and - as in your case - even educational :)

[JesseAStern]

How long did this project take and how much did it cost? I have to talk to a lot of laymans when explaining complexity theory and this is just a fantastic way to begin conceptualizing an otherwise theoretical model. Also, did you implement the blank symbol by representing it as being a lego that is neither in the 1 or 0 state (so in the middle of the row and therefore setting of both sensors) because if so that would allow for a lot more possibilities (as otherwise its just an LBA).

[andnissen]

We did the project over the course of half a semester, i.e. about 2 months. We used a Mindstorms 2 educational package consisting of a standard Mindstorms 2 set and another box of additional sensors etc..

Regarding blank symbols, we can use an arbitrary number of bits (LEGO blocks) to encode each cell. Using a cell-size of two bits, we can choose that the blank symbol is encoded by 00, and true is 01, false 10 and still have 11 available as additional data.

[MMcC86]

My life is (Turing) complete.

[xXbrokenskaterXx]

But can it run Crysis?

[MrDubbelodub]

@RedluckyMAN @pokemonhunt97 is right... 5 is an odd number.. 1,3,5 ... I just looked it up now.

[massacrealucard]

awesome, this is very amazing!!! =D

[LimitedWard]

Now make it sequence the human genome.

[GoldStarPL]

muzyka rozpierdala ^^

[antediluvian99]

Hey!! It's Alan from Cryptonomicon!!

[AceTracer]

This might be the only time I approve of the music in a YouTube video.

[tribeking100]

@andnissen whats a Turing

[baldaiaj]

I don't get it?

[pokemonhunt97]

@REDluckyMAN 5 is a odd number 1,3,5