4.1 One-Tape Turing Machines 161
S is a transition function. (Because the blank symbol B and the final state h
are common to every DTM, we do not need to define them here.)
Next, we explain how a DTM M accepts an input string 2.
First, how does a DTM start? Initially, we assume that the machine is in
the initial state s and the input x is stored in the second to (n + 1)st cells of
the tape, where n = 1x1, and the head is scanning the (n + 2)nd cell of the
tape. The first cell as well as all cells to the right of the (n + l)st cell are
assumed to have the symbol B. Figure 4.1 shows the initial configuration of a
DTM with input zu = abba.
In order to explain how a DTM &? operates on an input z, we need to
establish a notation to describe the configurations of a one-tape DTM M.
Assume that at some point, a DTM M is in a state q, its tape contains symbols
x1x2 l l l x,BBB + -0, wherexiEI’fori=I ,..., m-l,andx,EI’-{B},and
its head is scanning the kth cell. Suppose that m > - Ic, then we write(4,X1X2 ’ l ’ ~k-l,~k,~k+l~k+2*‘*~m)
to denote this configuration. If m. < k then we writek-m-l
to denote this configuration. In other words, a configuration of a DTM is a
string in
Q x I’ x I? x (I’(I’- {B}) U {E}).
A configuration (q, x1 l l. x&l, a, y1. l qrn) denotes that the machine is in
state q, its tape contains symbols x1. l l ~k-layl l l ymBB l l l , and its head
is scanning the kth cell (which contains symbol a). For instance, the config-
uration shown in Figure 4.1 can be represented by (s, Bubbu, B, E).
For each configuration (q, x, a, y), we also use the abbreviation (q, xuy) - or
xquy to represent it. (Note: If Q n I = 0, then the second abbreviation
presents no ambiguity.) So, (s, Babbu, B, E), (s, BubbuB) - and BubbasB all repre-
sent the same configuration of Figure 4.1.
Using this notation, the effect of each move of a DTM can be formally
described I as follows:
(1) At a configuration (q, x~~y), if d(q,u) = (p, b, R) and y # E then, after
one move, its configuration becomes (p, xbyly2) (called the successor
configuration of (q, xgy)), where y = yly2 an2 1~11 = 1.
(2) At a configuration (q, xu), if S(q, a) = (p, b, R) then, after one move, its
configuration becomes (p, x&).(3) At a configuration (q,xcty), if S(cr,u) = (p, b, L) and x # E then, after
one move, its configuration becomes (p, z,x,by) if y # E or b # B, or it
) if y = E and b = B, where = ~1x2 and 1x21 = 1.
(4) At a configuration (q,ay), if S(q, a> = (p, b, L) then the machine hangs,
or, halts without accepting the input. This configuration does not have
a successor configuration.