Read-Write-Erase

April 24, 2010 1:38 AM

A Turing Machine [SLYT].

More information on how the machine works. Example videos of the machine in action. Previously: Lego Turing Machine.

posted by daniel_charms (41 comments total)

Anyone else get a sense of irony here? That's the simplest of all possible computing devices, created with multiple machines that are billions of times faster. I found the idea of loading programs for your Turing machine from an SD card to be particularly amusing.

This is a great example of simplicity of concept not translating to simplicity of implementation. But, wow, that is one nicely-built machine.

Believe it or not, you could play Dwarf Fortress on that thing, if you had a few trillion years and a great imagination.
posted by Malor at 2:25 AM on April 24, 2010

You know what would be cool? Putting together a show with the Turing Machine and taking it to venues all over. Then they could call it The Touring Turing Machine.

And transport it around in a van like the one in Scooby Doo and call it The Touring Turing Machine Machine.

And of course, the Touring Machine Tour would have to stop in Turan, Italy.

And maybe it could join forces with MeFi's favorite Weird musician for the Al and Turing Machine Tour.
posted by oneswellfoop at 2:45 AM on April 24, 2010 [10 favorites]

oneswellfoop: First it'd have to figure out the shortest route to get to every city exactly once, though.
posted by cthuljew at 3:20 AM on April 24, 2010 [8 favorites]

What a waste of time. I can respect the ability of someone to design something like this, but the fact that this is what they decided to do with their time and ability is disgusting.
posted by TheCoyote23 at 3:31 AM on April 24, 2010

Really? I think turning the thought experiment behind the founding principle of an entire academic discipline into a functional, elegant, and dare I say beautiful physical implementation is one of the more impressive mixes of art and science I've come across in some time.
posted by Skorgu at 3:57 AM on April 24, 2010 [20 favorites]

It's beautiful to look at but I agree about the irony kind of ruining the science part. Surely this could be made more simply (and by simply I mean more complicated on the surface, but with less "depth").
posted by DU at 4:16 AM on April 24, 2010

These MeFi SLYT bother me. I've had to watch Ninja Cats, Dog Sledding, and the Insane Clown Posse. When will it ever halt?
posted by twoleftfeet at 4:18 AM on April 24, 2010 [1 favorite]

I thought this was a little silly too, the whole thing is built with advanced computer technology. I mean, it uses OCR and a camera to read. It's really more of a 'demonstration' of a Turing machine then anything else. Also, his claim that this is the "First Ever" Turing machine also makes no real sense at all. It's just one of the most literal interpretations, in terms of appearance. But in my mind it's not a 'real' turing machine because it's built out of other computers, rather then simple circuits or hardware.

the fact that this is what they decided to do with their time and ability is disgusting.

Disgusting? Really? How on earth is this "disgusting"? That honestly makes no sense at all.
posted by delmoi at 4:18 AM on April 24, 2010

Tough crowd.
posted by odinsdream at 4:27 AM on April 24, 2010

TheCoyote23: "What a waste of time."

But just think, with the right tape, it could be programmed to automatically create "controversial" comments which could be used to derail threads, thus leaving you with more free time for eating cheetos and watching TV.
posted by idiopath at 4:35 AM on April 24, 2010 [10 favorites]

Is it really fair to say (as the "more information" link does) that "the tape is the computer"? Consider two versions of this machine. The one in the video takes a tape with the data 1011, modifies the tape to contain 1100, 1101, 1110, 1111, 10000, and halts. A trivially different machine would take that initial condition and modify the tape to count backwards (1010, 1001, 1000, 0111, etc.) or halt on the input, or infinitely many different things. What is the difference between the machine that counts up and the machine that counts down? It is the list of states that the read-write head can occupy. And that list of states seems to live entirely inside the microcontroller, which as Malor points out is also a Turing-complete finite state machine that happens to run much faster. (I count a read-erase-write-move at about three seconds, and the controller can supposedly run twenty million instructions per second per cog, so it is only sixty million times faster, not billions. Though if the characters are an inch square, that thousand-foot roll of film has about the same storage space than the controller's RAM.)

I think the execution here is gorgeous, and I'm not at all bothered by the use of a microcontroller to drive the read head, the servos, or the stepper motors. But it's kind of a swindle to also let the microcontroller hold all of the state transition logic and at the same time claim that the tape is more than just the working memory of the machine.

If Mike Davey wanted this to evolve more towards a mechanical Turing machine, a nice next step would be a mechanical implementation of the state transition logic. Instead of three text lines describing each state, I can imagine a section of prototype board connecting each possible tape input to the tape output and the next state of the read-write head. Maybe with some transistor or relay logic so that only the part of the board corresponding the currently active state is powered. Then you would alter the machine to do something different by building a new part for it, like any other machine that Turing or his contemporaries would have recognized.
posted by fantabulous timewaster at 4:42 AM on April 24, 2010 [3 favorites]

From personal experience demonstrating to visiting friends gadgets I've made, I predict this guy has a window of no more than fifteen seconds to describe his pet project before his guests eyes glaze over.
posted by digsrus at 5:00 AM on April 24, 2010

What a waste of time. I can respect the ability of someone to design something like this, but the fact that this is what they decided to do with their time and ability is disgusting.

Exactly. They could be playing golf.
posted by weapons-grade pandemonium at 5:17 AM on April 24, 2010 [1 favorite]

Would be more impressed by a universal turing machine.
posted by norabarnacl3 at 5:19 AM on April 24, 2010 [1 favorite]

This is really great, and I would totally build something like this if I had the time and ability. I love the idea of turning a theoretical, conceptual machine used to better understand computation into an actual physical machine.

It would be a little cooler if the state table was also in physical form. Maybe a state table whiteboard with a camera that travels over it in X and Y axes as required?
posted by FishBike at 5:55 AM on April 24, 2010

But in my mind it's not a 'real' turing machine because it's built out of other computers

Indeed, and more fundamentally, it's not a real Turing machine because it doesn't have an infinite tape and it can't go on performing with perfect efficiency forever; and for that matter it isn't really even a discrete state machine. If to be a computer is to be a universal Turing machine (and I think it is) then strictly there are no real computers at all, just machines that approximate computerhood well enough to have some practical use.

Still, it's rather nice.
posted by Phanx at 6:03 AM on April 24, 2010 [2 favorites]

and the controller can supposedly run twenty million instructions per second per cog, so it is only sixty million times faster, not billions.

I was thinking mostly of the camera when I said that. Plus, most SD cards now come with very quick little microcontrollers on them -- it's cheaper to put a little CPU on the card to handle manually detecting errors and remapping sectors than it is to actually test the flash.

Further, each 'operation' of the Turing machine can only work on a single bit, so it could easily take 30+ minutes to duplicate a complex 32-bit instruction. The processor in the camera is probably 32-bit, and probably runs well north of 25Mhz, so I stand behind the 'billions of times slower' assertion.
posted by Malor at 6:33 AM on April 24, 2010 [3 favorites]

We need one of these in every classroom.
posted by mccarty.tim at 6:35 AM on April 24, 2010 [3 favorites]

timewaster: To be true to the spirit of the original idea, instead of actually rebuilding a mechanical transition function for each program, what would make the most sense would be to build just one mechanical transition function: one for a universal Turing machine. That way, you could load the program up by writing it on a tape, instead of building a new program for each machine. And in that case, you really could describe the tape as being the computer in some meaningful sense (certainly not the only meaningful sense, of course).
posted by ErWenn at 6:35 AM on April 24, 2010 [1 favorite]

Wouldn't some people argue that anything from this universe would be a computer? I mean, you can perform quantum computations with a hydrogen atom, and you can work out some force equations with a rock. Feed data, get result.

Thus, I have to say, it's very much a computer in spirit. And it's better than the sum of its parts, as you can clearly see how its doing what it's doing. As a computer meant to illustrate how a Turing Machine works, it does a great job.
posted by mccarty.tim at 6:38 AM on April 24, 2010

Step 2: Build a working China Room.
posted by mccarty.tim at 6:39 AM on April 24, 2010 [4 favorites]

Don't feed the troll.

I'm actually just fine with the idea of calling this device a Turing machine. Regardless of its actual implementation (and not counting the finite tape), the Turing machine is the right abstraction to use when thinking about what this device does and how to use it---you could say it passes the Turing machine Turing test. To be comfortable with computing, you have to be comfortable with abstraction anyway---I might even go so far as to say those who object to the behind-the-scenes details are missing the point!
posted by tss at 6:45 AM on April 24, 2010

Turing would have loved it.

In the draft designs for the Pilot ACE, he was very clear that the mechanical embodiment of the machine had nothing to do with the principle behind it. He even made jokes about building a computer out of steam engines and using books for storage.
posted by warbaby at 7:13 AM on April 24, 2010 [1 favorite]

I had a compsci professor in college who, I felt, got a huge kick out of Turing machines. I didn't understand it at the time, still don't quite. He would gleefully contend that the absolutely sweet (at the time) Athlon 64 processor w/ 2 gig of ram that I was running Linux on was nothing more than a hideously fast Turing computer. I think I took it the wrong way... but I felt that he was saying that my Precious Baby wasn't more important than a piece of paper tape.

I think he would enjoy this video.
posted by Severian at 7:53 AM on April 24, 2010

This thing is beautiful. It's also a great visual aid to internalizing the thought experiment, something that I daresay anyone who wants to work seriously with computers should do.

As for the criticism that the machines under the hood are vastly more complicated than the machine itself: so what?

Turing's thought experiment defined a set of instructions that a Turing machine needed to be able to follow. Turns out that following an infinitely variable matrix of instructions is actually a pretty complicated behaviour in and of itself. I've seen turing machine implementations where the read/write head was a person. Those work too.
posted by 256 at 8:00 AM on April 24, 2010 [1 favorite]

Surely this could be made more simply (and by simply I mean more complicated on the surface, but with less "depth").

That wasn't the point. The point was to make a machine that "embodied the classic look and feel of the machine presented in Turing's 1937 paper on computable numbers." This is why it has the tape, and the tape head that can read, write and erase.

It even has the correct property of the tape. The tape wasn't defined explicitly as infinite length, but as finite with the ability to add blank tape at the ends as needed, which is a subtly different property. Of course, this machine can't handle indefinitely extending the tape (nor could *any* physical machine, of course) so technically it isn't a true Turing Machine -- but no physical object can match the theoretical Turning machine in terms of capacity, because the theoretical Turing Machine has infinite storage.

So, this an analog representation of Turing's theoretical construct. And, as such, it's brilliant.
posted by eriko at 8:06 AM on April 24, 2010

I would like to point out that the Parallax Propeller which runs this thing is absolutely the most beautiful real CPU I have ever encountered. Each of the 8 cogs only has 512 32-bit instructions of native program RAM, but because the address space is so small those words are *extremely* powerful. Any normal person would look at the specs and ask WTF but once you get what the chip is about, it is amazing and there is nothing else out there even close to it.

And yes, this is a Turing machine, lacking only the infinite tape to be an extremely pure implementation. The fact that the machine driving the tape is far more complicated than the tape itself does not matter, as tss and warbaby have said that does not affect the principle at all and Turing himself understood this.
posted by localroger at 8:09 AM on April 24, 2010

All that effort and ingenuity, and the thing still can't tell you whether or not it's Numberwang?
posted by Crane Shot at 8:43 AM on April 24, 2010 [1 favorite]

The tape wasn't defined explicitly as infinite length, but as finite with the ability to add blank tape at the ends as needed, which is a subtly different property.

Never heard that before, and I think you're mistaken. See the 1948 paper here where Turing refers explicitly to an infinite tape.
posted by Phanx at 9:03 AM on April 24, 2010

Oh, man, this is a lovely piece of engineering. Arguing the details is good nerd fun, yes, but as a clean execution of a pretty straightforward idea—"I'll actually build a Turing tape machine"—I have no complaints. The guy did a great job. I smiled.

Believe it or not, you could play Dwarf Fortress on that thing, if you had a few trillion years and a great imagination.

Eliminate the middle man, and just play Dwarf Fortress using Dwarf Fortress.
posted by cortex at 9:24 AM on April 24, 2010 [2 favorites]

Hey, guys, what if we're all inside a Turing machine running inside of Dwarf Fortress, running inside of Dwarf Fortress?
posted by mccarty.tim at 10:48 AM on April 24, 2010 [1 favorite]

In a similar vein, he's also made a machine that makes wooden nickels.
posted by warbaby at 10:56 AM on April 24, 2010 [2 favorites]

Am I the only one that was pleased by the contrast in tone between the narrator of this video and the previous FPP? If I had not visited the previous post first I may have found the tone of this narrator annoyingly bland, but in context it was kind of a relief.
posted by idiopath at 11:00 AM on April 24, 2010

The personality, appearance, life story, etc I had mentally created for the guy behind this video changed drastically after he said that the machine decides that what's written on the tape "needs changed."
posted by PhatLobley at 11:16 AM on April 24, 2010

My local library is so stupid it's only a lame approximation of the library of Babel I am disgusted.
posted by everichon at 11:22 AM on April 24, 2010 [1 favorite]

For some reason this video reminds me of a segment on an old school children's show. Which leads me to a happy vision of children being taught about Turing machines on Sesame Street. Lovely.
posted by MadamM at 12:05 PM on April 24, 2010 [1 favorite]

MadamM: well Turing did propose a version of the machine where humans did the erasing / writing / etc. - I can easily imagine Sesame Street making a video of a version of a turing machine that looked like a game for kids to play - I think that could be excellent.
posted by idiopath at 12:27 PM on April 24, 2010

Re: Sesame Street teaching Turing machines

They could just adapt the relevant scenes from Stephenson's The Diamond Age.
posted by ErWenn at 3:05 PM on April 24, 2010

ErWenn, yes, a universal machine with the program and data together would be terribly exciting, even if the state transitions for the universal machine were still buried in a solid-state processor.
posted by fantabulous timewaster at 6:11 PM on April 24, 2010

the perfect thing to watch after drinking
posted by rebent at 9:24 PM on April 24, 2010

OMG HE SAID "NEEDS CHANGED"

Second time ever I have actually heard that idiom used in real life!
posted by kenko at 9:58 PM on April 24, 2010