# Turing Machines

To simulate more general computational procedures than the finite-state machine can handle, we use a

**Turing machine**, proposed by the British mathematician Alan M. Turing in 1936. Turing machine is essentially a finite-state machine with the added ability to reread its input and also to erase and write over its input. It also has unlimited auxiliary memory. Thus, the Turing machine overcomes the deficiencies we noted in finite-state machines. Unlimited auxiliary memory makes the Turing machine a hypothetical "machine" -- a model--not a real device.

## Turing Machine

A Turing machine consists of a finite-state machine and an unlimited tape divided into cells, each cell containing at most one symbol from an allowable finite alphabet. At any one instant, only a finite number of cells on the tape are nonblank. We use the special symbol b to denote a blank cell. The finite-state unit, through its read-write head, reads one cell of the tape at any given moment (Figure 9.15).By the next clock pulse, depending on the present state of the unit and the symbol read, the unit either does nothing (halts) or completes three actions:

1. Print a symbol from the alphabet on the cell read (it might be the same symbol that's already there).

2. Go to the next state (it might be the same state as before)

3. Move the read -- write head one cell left or right.

We can describe the actions of any particular Turing machine by a set of quintuples of the form

**(s,i,i',s',d)**, where s and i indicate the present state and the tape symobl being read, i' denotes the symbol printed, s' denotes the new state, and d denotes the direction in which the read-write head moves (R for ight, L for left).

the configuration illustrated in Figure 9.16b. The symbol 1 being read on the tape has been changed to a 0, the state of the unit has been changed from 2 to 1, and the head has moved one cell to the right.

## Definition

The restriction that no two quintuples begin with the same s and i symbols ensures that the action of the Turing machine is deterministic and completely specified by its present state and symbol read. If a Turing machine gets into a con- figuration for which its present state and symbol read are not the first two symbols of any quintuple, the machine halts.

Just as in the case of ordinary finite-state machines, we specify a fixed start- ing state, denoted by 0, in which the machine begins any computation. We also assume an initial configuration for the read-write head, namely, a position over the farthest left nonblank symbol on the tape. (If the tape is initially all blank, the read-write head can be positioned anywhere to start.)

The tape serves as a memory medium for a Turing machine, and in general, the machine can reread cells of the tape. Since it can also write on the tape, the nonblank portion of the tape can be as long as desired, although there are still only a finite number of nonblank cells at any time. Hence the machine has available an unbounded, though finite, amount of storage. Because Turing machines overcome the limitations of finite-state machines, Turing machines should have consider- ably higher capabilities. In fact, a finite-state machine is a very special case of a Turing machine, one that always prints the old symbol on the cell read, always moves to the right, and always halts on the symbol b.