Pirates & Revolutionaries: Programing Abstract Machines: Turing Machines in Boolos & Jeffrey's Computability and Logic

by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Central Entry Directory]
[Computation Entry Directory]

Turing Machines

Introduced by Boolos and Jeffrey

Our abstract machine is a man in a box. His cube travels along a railroad track.

The rail ties mark discrete squares along the track. The car may move along the track in either direction. We have rail workers on either end, always ready to add more track and ties as the box nears the edges.

Almost all the rail-ties have nothing but white ballast stones placed between them. But showing in a select few squares is one symbol from a finite set. They are configured using black ballast stones arranged against the background of the usual white ones.

The symbols in the square can be anything. And we will refer to them abstractly using variables, so to allow for every possibility. Hence we consider the finite number of symbols that may be found or placed in the squares S1, S2, ... Sn. The empty squares we will call S0. In our more concrete example, S0 will be a '0' in the square, and S1 will be a '1'.

The box's bottom is missing. So the man inside can read the symbols in each square. And he can change them or add a symbol to a blank square. The "poor mug" inside may also push or pull the box one place to the right or left. [below is a modification of the Boolos and Jefferey diagram. Image credits below.]

So the man performs his three actions: reading, writing, and moving. He does so according to a list of instructions. Any one instruction on the list has its own number i. He will be in a certain state at each stage of the computation process. What determines the state is the particular instruction he is performing. The total number of instructions is m. So we call the internal states q1, q2, ..., qm.

"He is in state qi when he is carrying out instruction number i."

Each instruction is formulated as a conditional. So it tells him what to do, depending on whether the symbol he reads is S0 or S1 or .... or Sn.

There are n + 4 things the boxed computer man can do. He can

1) Halt the computation.

2) Move one square to the right.

3) Move one square to the left.

4) Write S0 in place of whatever is in the scanned square.

5) Write S1 in place of whatever is in the scanned square.

n + 4) Write Sn in place of whatever is in the scanned square.

The instruction he carries-out is the state he is in. Depending on what that is, and on what symbol he is scanning, the man will perform one or some other of these n + 4 overt actions. And unless he is halted, he will also perform covert acts "in the privacy of his box." Namely, he will determine what will be the next instruction (the next state). "Thus, the present state and the presently scanned symbol determine what overt act is to be performed, and what the next state is to be." (22b)

There are a number of ways that we may specify the overall program of instructions the man is to follow. For example, we might use a machine table, a flow graph, or a set of quadruples. These three types of descriptions are illustrated below. This is how they appeared for a machine that writes three symbols S1 on a blank rail track, and then halts, scanning the leftmost of the three.

We will now look more closely at this example.

The man begins above an empty square (which we depict with a '0'). His instructions are, "if the square is empty, write symbol S1. And if there is a number S1 in the square, move one square to the left. Halt after writing three S1's"

More explicitly, when following instruction q1, the man is to

1) If the scanned symbol is S0, write an S1 in the initial square and repeat instruction q1. But

2) If the scanned symbol is S1, move left and following instruction q2 next.

So we will represent the instructions according to the three methods.

The computer box begins above a zero.

His initial part of his first instruction is a conditional. If it is '0', make it '1.' Then repeat instruction q1.

First the machine sees a zero. So it enters a '1'. Then it returns to the beginning of this instruction.

This first conditional of the initial instruction is displayed these ways for the different formats. In the machine table, we begin with q1. If it sees symbol So, he is to write an S1. The table displays the 'q1' in S1q1 to indicate that we go back to the beginning of the instruction.

In the flow chart, the circular arrow indicates the return to the same instruction.

And in the quadruples, the repeated q1 indicates the return to the instruction's beginning.

So the computer box returns to the beginning of q1. At the beginning, it says that if it reads S0, to write S1. But it does not read S0. The next part of the instruction says that if the symbol is S1, then move to the left and begin instruction q2. Thus our machine moves left.

We use an L to indicate the move-left operation in our three ways to show the program.

Instruction q2 is the same as q1, only one recurrence further in the process. Our computer sees a zero, so it enters a 1 and returns to the beginning of q2.