Small Universal Turing Machines
I ran across my copy of Marvin Minsky’s Computation: Finite and Infinite Machines. This isn’t exactly light reading, but it is far more accessible than some other treatments I’ve run across.
One of Minsky’s topics was just how small a universal Turing machine could be made. Briefly and broadly, a Turing machine is a formalism for encoding an effective method, a series of instructions that will perform a particular task, and a universal Turing machine is such a machine that is capable of computing any function that any other Turing machine can compute.
Our universal Turing machine has the property of simulating the behavior of any Turing machine with any input tape. […] Accepting Turing’s thesis, we conclude that the universal machine can simulate any effective process of symbol-manipulation, be it mathematical or anything else; it is a completely general instruction-obeying mechanism.
If I’ve counted correctly, Minsky’s example of a universal Turing machine in chapter 7 uses 7 symbols and 22 states. This, though, was done to make things easier to explain. One can (or at least Minsky and a few others can) substantially reduce both the number of symbols and number of states needed by sacrificing clarity of operation.
As Minsky notes, one needs a metric to decide what “small’ is, and in this book Minsky uses Shannon’s suggestion of the product of the number of symbols and states used by a Turing machine.
Chapter 14, “Very Simple Bases for Computability”, describes a small universal Turing machine (UTM), which, according to a 1991 paper by Raphael M. Robinson, remains among the smallest known universal Turing machines. Minsky’s small UTM has just 4 symbols and 7 states, for a total of 28 entries in its state-symbol table. Minsky’s discussion of UTM structure is interesting:
One might suppose, or hope, that the property that a Turing machine is universal should imply some interesting conclusion about its state diagram. But it seems that there is nothing much to say about this, in general, because there are universal machines with structures so trivial that one can draw no interesting conclusions.
[…]
There simply doesn’t seem to be any structure required that is any more complicated than one needs to make a multiplication machine.
As one wag put it, we don’t use Turing machines for real work since they are so lousy at input/output operations. Wikipedia notes this with the observation that one can “prove” pessimistic lower bounds on running times for certain algorithms based on the Turing machine formalism that are empirically disproved on our typical random access machines, which form the basis of the personal computer industry.
A TV biography of Turing some years ago noted that part of Turing’s motivation in thinking about computation was his loss of a close personal friend early in life. Turing, the show asserted, wanted to demonstrate that reasoning and thought could be given a simple physical basis, reasoning that life after death would be explicable on the idea that the simpler the basis for reason, the more likely it would be that transcendence could transfer the attributes and thoughts of a person to some other medium after the death of the body. If the TV program had that at all accurate, Minsky’s simple UTM probably would have gratified Turing.
