An actual Turing machine

Well, almost. Mike Davey wanted to outfit his gorgeous realization of Alan Turing’s foundational computer-science thought experiment (Wikipedia) with an infinitely long tape, but couldn’t afford to buy one. So he settled on a 1000-ft roll of white 35mm film leader. Can’t say I blame him. Have you priced infinitely long tapes recently?

All joking aside, this thing may be the most beautiful piece of kinetic art I have ever seen. It has a Cartesian robot to draw 1s or 0s on the tape as needed, a rolling felt-covered drum for erasing symbols, a camera that can recognize what symbols have already been written, a bank of white LEDs to provide illumination for the camera, and a beautiful custom control panel.

Mike himself says:

My goal in building this project was to create a machine that embodied the classic look and feel of the machine presented in Turing’s paper. I wanted to build a machine that would be immediately recognizable as a Turing machine to someone familiar with Turing’s work.

Although this Turing machine is controlled by a Parallax Propeller microcontroller, its operation while running is based only on a set of state transformations loaded from an SD card and what is written to and read from the tape. While it may seem as if the tape is merely the input and output of the machine, it is not! Nor is the tape just the memory of the machine. In a way the tape is the computer. As the symbols on the tape are manipulated by simple rules, the computing happens. The output is really more of an artifact of the machine using the tape as the computer.

So, in summation: Wow, Mike. You win. I’m never making anything again. [Thanks, David Jakopac!]

6 Responses to An actual Turing machine

Matt Mets on March 26th, 2010 at 2:23 pm said:

Absolutely beautiful!

…but can it run Crysis?

Reply ↓
seanpatgallagher.myopenid.com on March 26th, 2010 at 3:36 pm said:

So, if the tape drive jams, does that simulate quantum super-positioning?

It would be a Quantum Turing Machine!

-S

Reply ↓
Skyler Kehren on March 26th, 2010 at 5:35 pm said:

Great project and great presentation/video of it!

Reply ↓
EngineerZero on March 27th, 2010 at 11:17 am said:

Now, if Turing had added a second tape facing parallel to the first, and put toothpick rungs between them, and twisted the set-up along its length into a corkscrew . . . that would have been creepy.

Reply ↓
jason1729 on March 28th, 2010 at 7:23 am said:

It is a gorgeous machine, and obviously very well built.

But it is not “an actual” Turing machine. This particular device is mathematically equivalent to a Finite State Machine.

I don’t want to take anything away from the developer, I’m sure if I had the chance, I’d sit for hours playing with it, but why say “actual” instead of what it really is, which is a very nice demonstration of the concept. Just like those glass klein bottles which are not real klein bottles. but still are very nice for what they are.

Reply ↓
Sean Michael Ragan on March 28th, 2010 at 10:34 am said:

…the point of saying “actual” in the headline is to attract the attention of folks, like yourself, who know enough about the Turing machine to understand that there is no such thing as an “actual” one. So it’s sort of a cheap blogger trick, but, in my defense, I acknowledge it immediately in the first sentence: “Well, almost.” The rest of the first paragraph is about acknowledging that “almost,” as in the case of pretty much every purely mathematical construct, is as well as anyone can do in making the Turing machine “actual.”

Reply ↓