HP Forum Archive 21

[ Return to Index | Top of Index ]

(OT) Lego Turing machine Message #1 Posted by BruceH on 21 June 2012, 9:33 a.m. A Turing machine brought to life using Lego.

Re: (OT) Lego Turing machine Message #2 Posted by Luiz C. Vieira (Brazil) on 21 June 2012, 11:59 a.m., in response to message #1 by BruceH Thanks for sharing! Great stuff!!! I'll tell my students about it. Cheers.

Re: (OT) Lego Turing machine Message #3 Posted by Matt Agajanian on 21 June 2012, 1:24 p.m., in response to message #1 by BruceH Well, now I've seen (almost) everything. Fascinating and very cool! Thanks!

Re: (OT) Lego Turing machine Message #4 Posted by Paul Dale on 21 June 2012, 5:20 p.m., in response to message #1 by BruceH Pity about the Turing complete Mindstorms controller that powers it :-) - Pauli

Re: (OT) Lego Turing machine Message #5 Posted by C.Ret on 22 June 2012, 3:13 a.m., in response to message #4 by Paul Dale Hi I watched the video. The LEGO machine appears to be a robust mechanical of good composition. I like how the laser-diode cell immersed in at each reading and then quickly shrinks out to make room for the rotative manupilator hangs. But, I must have missed an important detail: it is the reading of the result: 2 + 2 = ? 4 ? The 2+2 was code as : + o o + o o + + + + + + ... But the "tape at end of the video" is showing samething like that : + o o + o o + o o o o o o o o o o o o o o o o I had expected something more like this: + o o + o o + o o o o + ? ? ? ? ? ? ? ? ? Apparently, I am in trouble at interpreting Turing's machine code ! C.Ret Edited: 22 June 2012, 3:14 a.m.

Re: (OT) Lego Turing machine Message #6 Posted by BruceH on 22 June 2012, 8:44 a.m., in response to message #5 by C.Ret The machine constructed only has data not code in the tape. The reasons given for this are a) that they didn't want people viewing the exhibit to be able to easily mess it up and b) they only wanted to use just one Mindstorms kit so didn't have space for a full version. As for the result, the video does highlight a bank of 4 switches as the answer. Perhaps you need to look again? ;-)

Re: (OT) Lego Turing machine Message #7 Posted by Rory Molinari (USA) on 22 June 2012, 9:33 a.m., in response to message #6 by BruceH I think that's OK. The standard model of a Turing machine doesn't have any code on the tape. The "code" is a table of (state, symbol, action) triples (or equivalent) which lives somewhere, which I've always mentally pictured as a kind of finite state automaton sitting next to and hooked up to the read head. A universal Turing machine - which can simulate any Turing machine, even itself - allows code to appear on the tape, but this is just code-as-data. The TM-simulation logic still exists off the tape. So I think it's fine to put the code (state machine) in the Mindstorms block. It would be cool to simulate the whole thing in Lego but I don't know what that would look like. Cheers

Re: (OT) Lego Turing machine Message #8 Posted by C.Ret on 23 June 2012, 12:35 p.m., in response to message #6 by BruceH OK! Thank you. I just review the video at a better Internet connection that allow me to stop, go backward and forward the video. You are right, in my first quick watch (at low speed connection), I miss a few detail, especially the state of the tape at the end of the process ( which have nothing to do with the 'tape' in the end-credit-generic) ! There is nothing wrong, apparently, the resulting state of the "computed" tape is + o o + o o + o o o o + + + + ... as one may expected. So, thank you for your analysis, sorry for my miss up first interpretation. And you are right, what is particular to Turing Machine is that the "paper" (or here "lego") tape is not the 'program', it is just the computation (or result of the computation). The program is somewhere else in the 'internal' ou 'mechanical' - for mechanical setup only - of the Turing machine. I still wonder how is such a ‘program’ looking, for example able to add two integer values and write the result in the format of this demo: a + b -> c express as : + o o ... o o + o o ... o o + o o o ... o o o + a times b times c=a+b times Example: + o o + o o + --> + o o + o o +o o o o+ 2+2=4 + o o o + o o + --> + o o o + o o + o o o o o + 3+2=5 + o + o o o + --> + o + o o o + o o o o + 1+3=4 How many internal states and transition rules? I know to program this on HP41C RPN-machine, but I am really poor in engineering such a program for a Turing-Machine!

Re: (OT) Lego Turing machine Message #9 Posted by BruceH on 23 June 2012, 8:52 p.m., in response to message #8 by C.Ret Mark Power wrote an article about Alan Turing, including programming a Universal Turing Machine on the HP41 in Datafile V28N5. You can buy the back issues from Jake Schwartz here.

Re: (OT) Lego Turing machine Message #10 Posted by Bill (Smithville, NJ) on 22 June 2012, 8:14 a.m., in response to message #1 by BruceH Another great page on the Turing machine and the creation of one: A Turing Machine Bill

[ Return to Index | Top of Index ]

Go back to the main exhibit hall