The Infinite Tape

I read most of The Annotated Turing during our Alaska cruise. In college they mumbled something about an infinite tape that a Turing machine could make marks upon and this represented all computers ever. It never made any sense to me.

The key thing that makes the Turing machine work - and which key fact was left out in the course I took - is the temporary storage. The temporary storage is every other square on the tape. Nobody in college said anything about temporary storage. Amusing, or, really, sadly, the cover of the book doesn't show the use of the temporary storage.

And where were the instructions stored? On a piece of paper, it turns out. And pattern matching is used to find the next transition, kind of like a Prolog predicate. And (generally) when Turning said computer he meant a person which was the traditional usage of the word back then. One of Turing's huge intellectual leaps was that the computer didn't have to be a person! Hence the test Turning invented about what makes a person a person and a machine a machine: the famous Turing Test.

My wife learned about Turning Machines in a class she took from Arvind. Apparently Arvind is not only a computer architecture genius but also a great teacher. I never met Arvind but I was caught up in the backwash of some of the work he did at UCI. I shared some lab space with a couple of guys - Curtis and and James (last names long since forgotten*) - who wrote a seven pass Dataflow compiler in Simula. (The language was called Id, for Irvine Dataflow.)   In the tradition of Turing, speed was not an issue. In other words, the entire thing was dog slow, but that wasn't the point.  I can't remember what it compiled Id into - either more Simula or PDP-10 instructions.  Most likely more Simula.

I think Dataflow as an architecture was put on commercial hold because chips just kept getting faster and faster without the need for parallel programming (in most cases). Now that all of those computer transistors are dedicated to parallelism perhaps Dataflow will come to the rescue as a computational model.

Anyway, great book!

Oh, and get this - it's by the guy that wrote all of those popular Windows programming books, Charles Petzold! Good work, Charles!

* I think this is James.

[Update: Check out this awesome video of a real life Turing machine that Braeden Shosa brought to my attention.]

Read Nano-Plasm on the Kindle

© 2005-2009 Stephen Clarke-Willson, Ph.D. - All Rights Reserved.