- One tape holds the "program." This consists of
a set of 5-tuples (old state, symbol read, symbol
to write, direction, new state).
- A second tape holds the current "state" of the Turing
machine that we are emulating.
- A third tape holds the "input" and will, upon completion, hold the "output." Again, since the tape alphabet of the emulated Turing machine may be larger than the tape alphabet of our universal Turing machine, we may need to encode the alphabet. (This is exactly analogous to using eight bits to represent an ASCII byte.)

We will not complete the development of a universal Turing machine, but it isn't as difficult as you might think. One of my textbooks has a complete universal Turing machine in only 23 states (and a reasonably small alphabet).

I have heard of a Turing machine that implements a FORTRAN compiler. Some people have too much time on their hands.

Copyright © 1996 by David Matuszek

Last modified Mar 27, 1996