[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.

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