Problem Solving in Automata, Languages, and Complexity

160 TURING MACHINES

B a b b a B B B

Figure 4.1: A one-tape DTM at the initial position.

(Figure 4.1). However, DTM’s can perform more functions than DFAs:
(1) The tape of a DTM is divided into infinitely many cells such that it
has a left end but is infinite to the right. Each cell can hold a symbol from a
finite tape alphabet I’. Symbols in r are divided into three groups: the input
symbols, the blank symbol, and the auxiliary symbols. The set C of input
symbols consists of all symbols that an input to the machine may have. The
blank symbol B # C represents an empty cell. The auxiliary symbols are other
symbols in J? - C - {B}.
(2) Th e a e ea t p h d can move along the tape, one cell per move, either to
the right or to the left. In addition to being able to read a symbol from the
cell it scans, the head can also erase the symbol in the cell and write a new
symbol there.

(3) The tape head is controlled by the finite control. The finite control

has finitely many states. Among them, there are two special states, the initial

state and the final state. The initial state is usually denoted by s, and the final

state is usually denoted by h. All states other than the final state form the

state set Q. After the head reads a symbol from the tape, the finite control

will tell the head the action to excute (i.e., to write a new symbol and to

move left or right) and change to a new state. These actions are described in

a transition function (or, the instructions)

6 : Qxr+(Quh)xI’x{L,R}.

An instruction S(q, a> = (p, b, R) (or, S(Q,U) = (p, b, L)) means that if at the

beginning of a move, the head reads symbol a and the finite control is in

state q, then the head changes the symbol a to b and moves to the right (or,

respectively, to the left) and the finite control changes from state Q to state p.

In summary, a one-tape DTM k2 can be described by a quintuple

M = (Q, C, W, 4,

where Q is a finite set of states, C is a finite alphabet of input symbols, r is

a finite alphabet of tape symbols with C U {B} C - I?, s is the initial state, and