[Overview] [Previous] [Next]
Universal Turing Machines II
It's a little easier to see how to build a universal
Turing machine if we use a three-tape Turing machine.
We have already noted that a multitape Turing machine is
equivalent to a standard Turing machine.
In fact, once you get into the details, it's probably
easier to do on a single-tape machine.
- 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