LEGO Turing machine crunches the numbers

A Turing machine is a basic device able to perform fundamental computing operations; they're super because they demonstrate the abstract concepts of compuer science in the flesh. Make's relentlessly wonderful catalog of strange machines today gives us one made of LEGO, by "Denis."
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.
How many billions of these would be needed to run Doom at at least 1 frame per universe? LEGO Turing Machine [Make]

About Rob Beschizza

Rob Beschizza is the Managing Editor of Boing Boing. He's @beschizza on Twitter and can be found on Facebook too. Try your luck at  
This entry was posted in Art and Instruments. Bookmark the permalink.

4 Responses to LEGO Turing machine crunches the numbers

  1. dculberson says:

    Smurf, thus letting the demons out into your research station, and starting real-life Doom!

  2. Anonymous says:

    Do you really think that your machine is euqivalent to a turing machine? What is the symbol beneath the stack? Is this the first symbol on the ground of the stack or what?
    Best regards
    Andre Betz

  3. Smurf says:

    You can’t run Doom on one of these machines: you’d need a stack so large it’d implode into a black hole.

  4. Brian Copeland says:

    Ack, where’s the video? That screams for a video.

    But in October 2007, someone finally proved that a 2 state, 3 symbol Turing Machine is universal. Given the example the author used, this one would certainly qualify. So that puppy can technically run any computable program.

    But wouldn’t Lego Star Wars be some recursive awesomeness?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


More BB

Boing Boing Video

Flickr Pool




Displays ads via FM Tech

RSS and Email

This work is licensed under a Creative Commons License permitting non-commercial sharing with attribution. Boing Boing is a trademark of Happy Mutants LLC in the United States and other countries.

FM Tech