Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Building a Turing machine

  1. Apr 13, 2009 #1

    daniel_i_l

    User Avatar
    Gold Member

    As a summer project I was thinking of building an entirely mechanical Turing machine - possibly with Lego. Has anyone attempted this? Does anyone have any advice on how to design this?
    Thanks.
     
  2. jcsd
  3. Apr 13, 2009 #2

    sylas

    User Avatar
    Science Advisor

    That's a great idea... but, yes, it has been done, by students at Aarhus University. They have a blog about it, at Lego of Doom, including a video of it in operation.

    Lego%20005.jpg

    Cheers -- sylas
     
  4. Apr 13, 2009 #3

    daniel_i_l

    User Avatar
    Gold Member

    Yes, but they used a computer chip to store the transition table and compute the next state. I want mine to be entirely mechanical.
     
  5. Apr 13, 2009 #4

    sylas

    User Avatar
    Science Advisor

    That would be very cool! Good luck.
     
  6. Apr 18, 2009 #5
    Danny Hillis wrote about building a tinker toy computer, and if I recall correctly, he said it was a big mistake not to include error correction. Keep that in mind when you build yours. And do share your results!
     
  7. Apr 19, 2009 #6
    Hi there, new to the forums, and I have a question...

    What exactly is a turing machine? I saw it one here and visited wikipedia. Is it basically a device that can perform a logical sequence of instructions with or without the need for a computer processor. So a completely mechanical turing machine would run on some sort of fuel, but actions and triggers etc. would be mechanically stored somehow?, like via a complex series of gears or switches?

    Glad to be hear and I would love to hear anyone's feedback.
     
  8. Apr 20, 2009 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    It's a mental experiment. There's no point* to building a 'standard' mechanical Turing machine, though every computer simulates one in a certain sense.

    * Except for a cool project like this, of course.
     
  9. Apr 25, 2009 #8
    WoW I saw the video, so cool.

    I would love to see the fully mechanical lego turing machine
     
  10. Apr 26, 2009 #9
    I assume you are meaning a mechanical universal turing machine, in which case it sounds great :) If you get it done, please post videos of it working :)

    I believe the analytic and difference engines designed by Babbage were entirely mechanical as well, although I don't think they were quite universal turing machines (namely, not completely general purpose).
     
  11. Apr 26, 2009 #10
    Is a Turing machine the same as a universal Turing machine?
     
  12. Apr 26, 2009 #11

    sylas

    User Avatar
    Science Advisor

    A universal turning machine is a set of transition tables for a turing machine. It means any other turing machine can then be encoded on to the tape, and simulated.

    A concrete representation in lego becomes a universal machine given the right transition tables. If the transition table is maintained on a computer chip, as in the Aarhus machine, there is no problem making it into a universal turing machine, although actually encoding a non-trivial machine onto the lego tape might be too big. If the transition tables are maintained in lego as well, then the universal machine transition tables might be more than you'd like to build.

    Cheers -- sylas
     
  13. Apr 27, 2009 #12
    Yup, the other way of thinking of it is that a universal turing machine is able to act as though it were any other turing machine given the right input. If you encoded each turing machine as a number Tn then a universal turing machine U would act on an input U(n) after which it would function as Tn

    It's basically what all computers emulate :) The encoding for a universal turing machine is pretty hefty though. I think I've seen a decimal encoding of a universal turing machine number (so an n in Tn specifying a universal turing machine) run on for several a5 pages.
     
  14. Apr 27, 2009 #13
    I seem to recall some rendition of a UTM that required only 22 or 24 quintets. (I haven't looked at this stuff since Turing died.)
     
    Last edited: Apr 27, 2009
  15. Apr 30, 2009 #14
    The main problem, as I see it, is where will you put the infinite-length tape?
     
  16. Aug 19, 2010 #15

    daniel_i_l

    User Avatar
    Gold Member

    Hi,
    In the end lego was too expensive so I used carboplast, popsicle sticks, plastic bottles, rubber bands and a glue gun. Here's the result:


    The turing machine in the movie can run down the track and flip bits according to a program determined by the wiring. Currently it can only execute simple programs because it doesn't have external memory. But that's theoretically simple to add because I'd just have to build another identical unit that operates on one bit only for each bit of memory.
     
    Last edited by a moderator: Sep 25, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Building a Turing machine
Loading...