Skip
# 0110000101101100011000010110111000100000011101000111010101110010011010010110111001100111

Actually, an unbounded tape is enough, as long as you extend it whenever you reach an end.

posted by erdferkel at 11:38 PM on June 19, 2012

Turing machines are a topic of computer science (i.e. math). I don't have a good reference for those to hand, unfortunately. I would also appreciate a popular, but thorough, treatment of these (and DFAs, NFAs, P vs NP, etc) to give to my computer-interested child.

If you want to know more about computer *engineering*, i.e. how do you put electrons in one end and get information to come out the other end by the use of logic gates and whatnot, then you want this book which starts with "how does a simple switch work" and goes all the way up to building a CPU on paper.

If you want to do more than build on paper and want to actually build (a simulation of) a real computer using the same ideas as from

posted by DU at 5:26 AM on June 20, 2012 [2 favorites]

Post

# 0110000101101100011000010110111000100000011101000111010101110010011010010110111001100111

June 19, 2012 8:02 PM Subscribe

Gahhh.

A "real" Turing machine isn't an actual physical device, it's mathematical.

A Universal Turing Machine can.

</pedant>

Now I'm done with that, this is nice. But minecraft turing machines are arguably more impressive, because they do have to "physically" represent the transition table. Doing so in Lego would be pretty impressive... I don't think I've ever seen a Turing machine physicalized without a microcontroller doing the heavy lifting.

I wonder how hard it would be to build the transition table for a FORTH-interpreting Turing Machine...

posted by BungaDunga at 8:45 PM on June 19, 2012 [1 favorite]

*It is a device that manipulates symbols on a tape according to a table of rules*A "real" Turing machine isn't an actual physical device, it's mathematical.

*It is able to simulate the logic of any computer program*A Universal Turing Machine can.

*Some*Turing Machine can simulate the logic of any given computer program. The talk of "The" Turing Machine just seems weird to me, it's not like there's only one of them.</pedant>

Now I'm done with that, this is nice. But minecraft turing machines are arguably more impressive, because they do have to "physically" represent the transition table. Doing so in Lego would be pretty impressive... I don't think I've ever seen a Turing machine physicalized without a microcontroller doing the heavy lifting.

I wonder how hard it would be to build the transition table for a FORTH-interpreting Turing Machine...

posted by BungaDunga at 8:45 PM on June 19, 2012 [1 favorite]

Yeah... a "real" Lego Turing machine should have it's states and transitions coded in bricks, rather then having it all done using another computer. It's really more of a Turing machine "simulator", Turing the actual logic inside another computer, and the output is really just a visual representation of what's going on in the virtual TM.

Anyway, found this Lego difference engine clicking around youtube. That's kind of cool.

posted by delmoi at 11:30 PM on June 19, 2012

Anyway, found this Lego difference engine clicking around youtube. That's kind of cool.

posted by delmoi at 11:30 PM on June 19, 2012

*A real Lego turing machine would have an infinite tape.*

Actually, an unbounded tape is enough, as long as you extend it whenever you reach an end.

posted by erdferkel at 11:38 PM on June 19, 2012

aaaand here's an actual analytical engine (supposedly) built out of something called meccano

And now I'm down the rabbit hole

posted by delmoi at 11:49 PM on June 19, 2012

And now I'm down the rabbit hole

posted by delmoi at 11:49 PM on June 19, 2012

I came to this thread to make pedantic objections, but I have been rendered otiose.

posted by Segundus at 12:02 AM on June 20, 2012 [1 favorite]

posted by Segundus at 12:02 AM on June 20, 2012 [1 favorite]

If I can just live my life without seeing one more goddamn Lego anything, I will die a happy man.

posted by Max Udargo at 12:41 AM on June 20, 2012

posted by Max Udargo at 12:41 AM on June 20, 2012

I am still amazed gob how people figured this stuff out.

Is there anywhere I can read about Turing machines and basic computer processes in general? I find it facinating, but I am having trouble finding a good starting

point/introduction to this sort of thing. Everything I find seems to require prior knowledge of other computer processes and I don't know where to start!

posted by littlesq at 3:20 AM on June 20, 2012

Is there anywhere I can read about Turing machines and basic computer processes in general? I find it facinating, but I am having trouble finding a good starting

point/introduction to this sort of thing. Everything I find seems to require prior knowledge of other computer processes and I don't know where to start!

posted by littlesq at 3:20 AM on June 20, 2012

*gob = a word my phone decided to insert

COME ON

posted by littlesq at 3:23 AM on June 20, 2012 [3 favorites]

COME ON

posted by littlesq at 3:23 AM on June 20, 2012 [3 favorites]

*Is there anywhere I can read about Turing machines and basic computer processes in general?*

Turing machines are a topic of computer science (i.e. math). I don't have a good reference for those to hand, unfortunately. I would also appreciate a popular, but thorough, treatment of these (and DFAs, NFAs, P vs NP, etc) to give to my computer-interested child.

If you want to know more about computer *engineering*, i.e. how do you put electrons in one end and get information to come out the other end by the use of logic gates and whatnot, then you want this book which starts with "how does a simple switch work" and goes all the way up to building a CPU on paper.

If you want to do more than build on paper and want to actually build (a simulation of) a real computer using the same ideas as from

*Code*, then you want this book which guides you through creating logic gates, memory units, CPUs and finally a computer.

posted by DU at 5:26 AM on June 20, 2012 [2 favorites]

For a fun time with simple logic, kohctpyktop is a nice sim. Not completely electrically correct, but the logic is.

posted by FireSpy at 6:19 AM on June 20, 2012

posted by FireSpy at 6:19 AM on June 20, 2012

« Older Rendered from simple html and css, it is the very... | In 2010 you loved "Valentine's... Newer »

This thread has been archived and is closed to new comments

Would like to see them come up with some way to encode the state register and transition table in physical Lego blocks, rather than just using an attached microprocessor to control it. Which kind of feels like cheating.

posted by axiom at 8:16 PM on June 19, 2012