A Universal Turing Machine
When I was in junior high school, I became interested in computers. After learning BASIC on TRS-80s and Commodore PETs, I started doing all sorts of projects. One of the more memorable ones originated in the basement of my parents' house.
The basement held my parents' library. My mother's taste ran the gamut from art and theology to Anthony Trollope, while my father's collection was mostly textbooks. Since we're both tech types, I found his books more interesting (once I'd learned algebra, of course). One that caught my attention was a book on the theory of computing called Formal Languages and Their Relation to Automata by Hopcroft and Ullman. It taught me about the various kinds of theoretical machines (pushdown machines, multi-tape machines, etc.) and some language theory. I was most interested in the information on Turing machines, though. Imagine: a simple theoretical machine that can in theory calculate anything that any other machine can! Now that's an intellectually exciting notion.
The book also discussed what is known as a universal Turing machine: a Turing machine that, given the description of any Turing machine and its starting tape, will simulate that machine. Neat. And, best of all, the book had a three-page table of the states and transitions of a universal Turing machine. So of course I had to implement it. It wasn't too hard, even in BASIC. I translated the state table into a machine-readable format. When it was all done, I typed in the word RUN and hit the Enter key. To my delight, the universal Turing machine began running, with the changing tape displayed before my eyes.
...and then it stopped unexpectedly.
What was going on? It seemed stuck. I checked the implementation and it was correct. The problem soon became obvious: the book was wrong. With the modification of a transition or three, the universal Turing machine ran correctly. Hoo-ha! Quite neat. I had to wonder, though, how many people ever found that error.
The years passed, but I didn't forget universal Turing machines. I thought about them again this year while visiting Powell's Technical bookstore in Portland. Sure enough, they had a copy of Hopcroft and Ullman, so I looked for the UTM state transition table. To my consternation, I couldn't find it. Then it hit me: the authors must have removed it in a revision. It makes sense, in a way; it's three pages long, and it's very probable that only a small number of readers ever did more than glance at it. And so it disappeared.
Since then, I've been hankering for a working UTM again. The original edition of the Hopcroft & Ullman book was impossible to find locally, and my father's copy has disappeared, so I started creating a UTM of my own based on what I remembered of Hopcroft & Ullman's original. I'd completed about a third of it when I ran across a 1969 copy of the book in Powell's Technical. It was $20, though, and I didn't want to spend that much just to get three pages. However, the next day, I discovered that a neighbor who is a computer science professor had a 1969 copy. Within a few days I'd implemented the UTM and corrected the state table.
If you're interested in implementing this, here's the tape encoding and starting information.
If you want to play around with this, here's the source code. It was written in Turbo Pascal 3.01, a now-retro 1985 compiler. (Back then compilers could fit on one 5 1/4" floppy. Can you imagine that?) To advance to the next state, hit any key. Holding down any key gives a zippy little animated display. I've left the debugging information in; figuring out the tape-symbol-to-actual-code is left as an exercise for the reader*. The code's very sloppy, since I just wanted to get something working in order to correct the state table. For example, it will barf if the input tape is more than 70-odd characters long. That's life. Feel free to improve it.
If you don't have Turbo Pascal, here's the program as a 14K MS-DOS COM file. You'll also need to download the state table. Finally, here's an example input tape. (Note: if you want to create your own input tape, you must name it emulated.tm.)
Amusing side note: I recently looked at the text on formal languages and automata that's used by the computing theory course at the local university. There's a whole section on UTMs, but the author (Peter Linz) dismisses the creation of a state transition table for a UTM as "uninteresting". Speak for yourself, Mr. Linz. You should encourage your readers, instead of dismissing projects they might be interested in trying.
Another side note: Turing machines play a role in Neal Stephenson's science fiction novel The Diamond Age. In it, a young woman learns programming by creating successively more complex Turing machines. While this is theoretically possible, it's obvious that Mr. Stephenson's never actually programmed them himself. If he had, he would quickly have realized that no one programs Turing machines in the real world. While they are a fundamental part of computing theory, creating a Turing machine that does anything but the simplest operations is an exercise in extreme bookkeeping and tedium. Stephenson's technical gaffe destroyed my suspension of disbelief, something that is critical to becoming involved in a story. No doughnut for you, Neal.
Notes
* I've wanted to use this phrase for the longest time. Oh, wait... I already have.
Last updated 13 November 2000
http://www.rdrop.com/~half/General/UTM/index.html
All contents ©2000-2002 Mark L. Irons.