In this supplement to my notes, I will describe one version of a Universal Turing machine. Though not the "smallest", it is one of the clearest and prettiest I have seen.

Is it important to know the details? No; nor will they be the subject of exam questions. The important thing is that such a machine exists.

Nonetheless, it is fascinating that so simple a machine (only 23 states and 8 symbols if I have counted correctly) can be a UTm. Appreciate what this means. If Turing's Thesis is correct, this tiny machine can carry out EVERY computation which can be described by an effective procedure.

I hope some people will be sufficiently intrigued to study the machine a little, and try to work out how each section operates. Actually, when you first study a section, you might well miss one or two subtleties (I certainly did!), which you realize only on a second reading. I will add a detailed description of one section at the end.

Of course, the machine is very slow. It acts as an interpreter, obeying a single quintuple of the simulated machine for each major loop around the UTm (anticlockwise). Some of the main subsections also involve loops, and so do most of the states within these subsections. Not only this, but there are deeper levels of interpretation. Given an arbitrary Tm, we may first have to simulate this by a Tm with a singly-infinite tape, and then simulate this new machine with another which uses only two tape symbols. Only then can we simulate this machine, in its turn, using the UTm.

As I have said, this is not the smallest known UTm. Minsky himself described (7 state, 4 symbol) and (6 state, 6 symbol) machines, but these require some additional concepts too extensive to repeat here.

I will distribute an annotated diagram of Minsky's UTm in hardcopy. Let us call it U. On U's tape we place a description of any other Tm (let's say T), consisting of a list of T's quintuples, T's current state, and a description of T's current tape. U simulates T step by step, and therefore computes whatever T is computing. Every complete tour around the U modifies the current state and the description of T to advance T by one moment.

U's tape

U's tape is shown at the bottom of the figure (broken into two merely to get it on the original page).

Minsky assumes that T has only a binary alphabet, and a tape infinite in only one direction (leftwards). But this, of course, is not really a restriction (see topics 18a and 19). The lefthand part of U's tape contains a copy of the tape of T, with one difference: the position of T's head is marked by a special symbol M, and the binary digit which should be in M's cell is actually stored immediately to the left of the leftmost X.

T's states are numbered, and are represented by binary integers. In this illustration, two bits are used (so T has 4 or fewer states), but nothing in the operation of U prevents this being any number of bits one wants, as long as it's the same everywhere on U's tape. The current state of T is stored to the right of the lefthand Y. The quintuples of T appear (in any order) on the righthand section of U's tape. Each is a binary string of size 2p + 3, where p is the number of bits needed for the state.
L and R are represented by 0 and 1 respectively. The quintuples are separated by X's, and the rightmost is terminated by a Y.

Minsky's form of Tm

Minsky draws his Tms in a form similar to an fsm. Every state is represented by a little hexagon. The arrows which leave the states represent the quintuples. Each has a symbol on its tail (the symbol being read) and another along the path (the one being written). Occasionally an arrow has more than one tail symbol, and represents more than one quintuple.

One curiosity: you would expect each quintuple to contain a direction. But Minsky imposes a voluntary extra restriction on himself. He constructs Tms so that all arrows entering a particular state have the same direction. So he puts the direction, L or R, on the state being entered, instead of the arrow. This is actually not as strange as it seems. When you study his machine (and indeed many Tms), you realize that every state corresponds to some tape scan either to the left or to the right. We go right looking for B. When we find one we continue right looking for 0, or go back left looking for X. So the fact that states can be labelled as leftward or rightward scans is not surprising. Oh, by the way, his restriction allows him to leave out of the diagram arrows which simply cause the head to skip a cell on the tape, i.e.

Other comments

A few other comments may be helpful in understanding the operation of U.

U uses A's and B's as alternate forms of 0's and 1's. As it passes across 0's and 1's, it sometimes changes them to A's and B's, preserving the information, and at the same time, marking where it has got to. Or vice versa. Eventually it must ensure that the tape is restored to its 0's and 1's form for the next round.

Several of the regions of U have a local symmetry. When U wishes to remember whether it has seen a 0 or a 1 while moving from one part of the tape to another, it does so by being in one or the other half of the symmetric pattern.

U starts with its head on the leftmost X.

The numbered triangles are spurious, and relate to commentary in the original description. The broken lines merely divide the diagram into its major sections, which were also separate figures in the original presentation.

My handwritten comments refer to nearby states and give the broad picture.

Detailed description of 6.1-5

Label the states by their position in Fig 6.1-5 as follows:

               3


        2                5            6


               4                      1

In state 1, the machine crosses the machine condition section changing 0's and 1's to A's and B's. On finding the Y, it moves right (now in state 2) and picks up the first (actually, the next) A or B changing it back to 0 or 1, and remembering which one it found by being in state 3 or 4.

In state 3 or 4, it tries to match the machine condition symbol it is remembering with the next {0,1} symbol in the quintuple section. If it finds a match, it goes to state 5; a non-match, to state 6. (During this scan, it passes over the rest of the machine condition section, and also any quintuples which it has previously failed to match, because these have A's and B's in place of 0's and 1's.) If the match succeeded (state 5), it returns to the lefthand Y, and then moves right (state 2 once again) to pick up another symbol of the machine condition. Note that the quintuple symbol matched last time is now A or B, and so it too will be passed over this time. Note too that if, during its attempt to pick up a machine condition symbol, the machine finds X, it has successfully matched the whole machine condition to quintuple, and it can now proceed to the next stage (Fig 6.1-6); the quintuple dictionary, including the QS part of the successful match, has been changed to A's and B's, and this marks the position of the success.

Back to state 6. Here we failed to match a machine condition symbol to a quintuple symbol, so we wish to try the next quintuple. We proceed forward to the end of the quintuple (symbol X), then back across it (state 1) changing the rest of it, and later the matched part of the machine condition, to A's and B's. Then, starting again in state 2, we attempt to match the machine condition to the next quintuple. Note finally that if we encounter Y (the righthand Y) when looking for the end of the failed quintuple (state 6), there are no more quintuples to search (i.e. no quintuple matches QS), and the machine halts.