# Universal Turing Machines

In the last module, we wrote out the states of the machine table in terms of four letters: 'P', 'E', 'R' and 'L', along with a number for designating the state the machine should enter upon completing these instructions. But this combination of letters and numbers are symbols - just like the sequences '011' upon which the rules operate. That means if we can transform our definition of a machine table into a set of symbols the machine can process, the machine could read in its own machine table. Remember that the machine table defines the function of the machine. So, if we could create a machine that could read any machine table, and then follow the rules it defines, we could create a machine that could emulate any Turing machine. Such a machine is called a Universal Turing Machine. Your computer is a kind of Universal Turing machine (although it has a Random-Access Memory (RAM) that Universal Turing machines do not).

Recall that the structure of a machine table pairs states and the values read off a tape. Consider the following 2-state machine table:

 Value 0 Value 1 Machine Table for Counting in Binary State 0 EL1 PR2 State 1 PL1 ER2

Here's the machine in action:

Simple Binary Counting Turing Machine

In order to encode the machine table into symbols that can be feed into the machine itself, we need first to come up with a system for specifying the state–value pairs that determine the rows and columns of the machine table. In this case, we have 2 states (0 and 1) and two values (0 and 1). There are four possible combinations of states and values: 00, 01, 10, and 11 (state listed first, input listed second, so that this representation reads across the rows of the table). Let us specify cells of the machine table in this way. The machine table above becomes:

 Value 0 Value 1 Machine Table for Counting in Binary State 0 1EL 2PR State 1 1PL 2ER

Or, written out as a string:
00: 1EL, 01: 2PR, 10: 1PL, 11: 2ER

Note that we moved the 'goto state' specifier to the beginning of the command string instead of the end. This is simply a matter of convention.

As we have changed the states from '1' and '2' to '0' and '1', we need to update our table thus:

 Value 0 Value 1 Machine Table for Counting in Binary State 0 0EL 1PR State 1 0PL 1ER

Or, written out as a string:
00: 0EL, 01: 1PR, 10: 0PL, 11: 1ER

Each cell of the machine table specifies three things:

• Which state to enter once the instructions are complete (now 0 or 1)
• Whether to print (P) or erase (E) the value on the tape.
• Whether to move Left (L) or right (R).

Each of these instructions is an either-or value, and as such, can be represented in binary notation. So we change the instructions to this:

• Which state to enter once the instructions are complete (0 or 1)
• Whether to print (1) or erase (0) the value on the tape
• Whether to move Left (1) or right (0).

We can then specify the machine table thus:

 Value 0 Value 1 Machine Table for Counting in Binary State 0 001 110 State 1 011 100

Or, written out as a string:
00: 001, 01: 110, 10: 011, 11: 100

Now, for the sake of simplicity, we'll drop the colons, and separate the 'cells' of the machine table with the character 'X':

X00001X01110X10011X11100X

You'll notice that the machine table is bounded on both sides by an 'X'. These X's tell the universal machine where it's table starts and stops.

This string can now be written out to a tape. To see how it is computable by a Universal Turing machine, we need to make a few more changes to our machine.

First, we need to divide the tape into two sections — one containing the machine table (the string we just formed above), and one containing the area in which the computation will be performed. We'll separate these two sections by adding tape block marked 'Y. We also mark the starting point for computation with an 'M'':

Universal Turing Machine set-up

The tape stretches infinitely to the right. To the left, it contains only enough tape to hold the instruction string we formed above.

We then block off two tape blocks immediately to the left of the "Y". These will record the current state of the machine and the character to be printed when it completes its computation. Once it has finished its computation, these squares hold the represent the state-value pair that specifies a unique cell on the machine table. Thus, by reading these squares and looking for a match in the string we formed earlier, the machine will be able to find which instruction it should follow.

Universal Turing Machine Set Up, Part 2

Now, we load the machine table string into the left portion of the tape, being careful to reverse the order. We have to do this because in this portion of the tape, the machine reads from right to left. In the other portion of the tape, it reads from left to right.

The two digits between the 'Y' and 'X' hold information regarding the current state of the machine, and the last value read from the tape. The first step in the cycle, then, is simply a matter of having the machine read in its current state and value, and find the corresponding set of instructions for that state. Once it has found the instructions, it has to record (a) the next state to go in to, and (b) the value to write out on the tape. It does this via the 'Copy' and 'Locate and Copy' phases. Once all of this is complete, it can work on the computation itself. Once the computation is complete, it reads in the next square, and writes that in the square that contains the machine's current value. Now, the machine is set up for the next cycle: it has information regarding the current state, and the last value read.

A Universal Turing Machine

Specification of this Universal Machine adapted from Minsky, Marvin L. (1967) Computation: Finite and Infinite Machines, p. 137-145)

As the machine operates, you'll notice that it cycles through a series of phases. These are not rules in the conventional sense, as they do not directly impact the particular computation. Rather, they are activities of the mechanism, by which the particular computation can be processed. They are listed in order here:

• First, it starts at 'Y'. It starts by entering it's 'Locate' Phase
• Locate: It reads in the values of the numbers between Y and X, and searches to the left until it finds a match for these two symbols in this order, and immediately following a 'X'. As it moves, it turns 0's to A's and 1's to B's, just to keep its place. Once it find a match, it proceeds one more square to the left, reads and remembers its value. It then enters the 'Copy' phase:
• Copy: It proceeds to the right until it finds the 'Y'. Once it has found 'Y', it turns to the left again, and changes the first 'A' or 'B' it finds into the '1' or '0' it had previously remembered. If the machine does not hit and 'X' before it can print the remembered value, it goes into the 'Locate to Copy' phase. If it does hit a 'X' before it can print out the remembered value, it goes into the 'Find M' phase:
• Locate to Copy: The machine searches to the left until it finds a digit. Once it does, it reads and remembers this digit, replacing it with an 'A' or 'B' accordingly. It then goes back into the 'Copy' phase.
• Find M: Once it finds the 'X', it turns to the right and proceeds until it finds the 'M'. It then changes 'M' to 'A', if the remembered value is '0', and 'B' if the remembered value is '1'.
• Reset: The machine then 'resets' — it proceeds to the left changing all A's to 0's and all B's to 1's. If it finds two digits (not either 'A' or 'B') in a row immediately following a 'X', or it finds a 'Z' (the end of the tape), then the machine goes into the 'Return to Base' phase.
• Return to Base: The machine has completed the reset and returns to the 'Y'. It then goes into the 'Compute' phase.
• Compute: It proceeds to the left, until it finds the first 'X'. When it does, it turns around, and reads and remembers the first digit it encounters. To keep its place, it marks that square with an 'S'. It proceeds to the right until it finds an 'A' or 'B'. When it does so, it replaces that letter with a 0 or 1 respectively. If the remembered digit was a '1', it proceeds to the right, reads and remembers the value it finds there, and writes out the 'M'. If the remembered digit was a '0', it proceeds to the left, reads and remembers the value it finds there, and writes out the 'M'.
• Read and Remember: It then returns to the 'S', and replaces it with the remembered value. It then goes into the 'finalize' state.
• Finalize: The machine returns to the 'Y', so that it can start the cycle again.