Problem Solving in Automata, Languages, and Complexity

4.3 Multi-Tape Turing Machines

(5) At a configuration (h, ~g), machine halts and accepts the input. This

configuration does not have a successor configuration.

If a2 = (P, u b w > is a successor configuration of a1 = (4, zay), then we write
a1 kM CE~. If there is a sequence of configurations al, CQ,... , an, n > 1, such
that ~i kM ai+l for all i = 1,2,.. ., n - 1, then we write a1 k: a,. When
the machine M is understood, we may simply write ~1 t- CQ and al c an to
denote al kM a2 and ~1 k; an, respectively.
Formally, a string x is said to be accepted by a TM A& if &! halts at state
h on input x:, or, equivalently, if (s, BxEJ) p (h, ygz) for some y, z E I’* and
a E I?. We say that the sequence of configurations in (s, BzB) p (h, ygz) is the
computation path (or, simply, the computation) of M on X. A string x is not
accepted by M if either %! hangs on x or A& does not halt on X.

Example 4.1 Let Ml be the one-tape DTM defined by the quintuple (Q, C,

I’, S, s), where & = {%ql,q2,q3,P}, c = {O}, r = {a, 0) md 6 is given

by the following table:

s

S

41

I

42

q3

P

U

P, u, R

41,aJ

421 a, R

P, u, R

P, a> R

b

P, b, R

41, b, L

Q3r b, R

43, b, R

P, b, R

Then, the initial configuration of Ml on input ubbu is exactly the one

B

Ql, B, L

q2, B, R

P, BY L

h,B,L

P,BJ

shown in Figure 4.1. In our notation, it is (s, BubbuB). - Starting from this

initial configuration, the computation of Ml can be described as follows:

(s, BabbuB) I- (ql, Bubbcz) I- (41, Bubbu) t- (ql, [email protected]) t- (ql, Bc#m)

t- (41, Babbu) t- ( q2, Bubba) - k (q2,Bubbu) - t- (q3, Bubbu) - I- (q3, Bubbu) -

t- (p, BubbaB) t- (p, Bubbcx) t- (p, BubbuI3) t- (p, Babba) - t- l..

That is, Ml will eventually enter state p and its head will move between the

fifth and sixth cells of the tape forever. In other words, Ml enters an infinite

loop on input ubbu.

On the input u3b the DTM Ml behaves differently:

(s, BuaubB) < (al, &mub) I- (q2, Bgd) t- (qz, Baaab) I- (qz, Baaab) -

I- (q2, BuO) t- ( q3, BuaubB) t- (h, Baud).

Thus, Ml accepts the input u3b. cl

In the above example, we see easily that once Ml goes into the state p, it
will be trapped in an infinite loop, that is, it never halts. In other words, the