..

Universal Turing Machines

Author: Peter Bradley

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:

Machine Table for Counting in Binary
 Value 0Value 1
State 0EL1PR2
State 1PL1ER2

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:

Machine Table for Counting in Binary
 Value 0Value 1
State 01EL2PR
State 11PL2ER

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:

Machine Table for Counting in Binary
 Value 0Value 1
State 00EL1PR
State 10PL1ER

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

Each cell of the machine table specifies three things:

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:

We can then specify the machine table thus:

Machine Table for Counting in Binary
 Value 0Value 1
State 0001110
State 1011100

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:

 


Copyright: 2002