Problem Solving in Automata, Languages, and Complexity

5.6 Undecidable Problems 273

(1)

[

H

.

[Bql1B*

for each a E r U { *}.

(4)

cqia ----

cqza

RR

and for

qjFb ’ qjcb

, for each instruction tY(qi, a) = (qj, b, L) of M

each c E r.

(5) H, Fi, El, Ei,foreachaH’.

(6) IFi , for each a E I?.

(7)

Qn+l*l

El^1

’

4n+l*]

El^1

.

We need to prove that M halts on x if and only if P, has a solution. First,

assume that M halts on x. We modify the definition of the configuration

of M to include all tape symbols in all cells that have ever been visited by

the tape head in the computation of M on input x. That is, the rightmost

blank symbols in a configuration are not removed in the representation of

the configuration. Assume that the computation of M on x consists of the

following configurations:

a0 t- cl!1 t- l l l I- at,

where a0 = BxqlB and CQ = y1 l l l ypqnxlx2 l l l zq, where each yi and each zj

is a single symbol in I?. Define CQ+~ = 2~1~2 l •yPqn~i+l l l l xq, for 1 5 i < q,

w.+q+1 = YlY2 l l aYpQn+l, and at+q+j = Yl ” ‘Yp+l-jQn+l, for 2 < - j < - P + 1.

We claim that if e + q + p + 1 is odd, then

is a solution to Pr, and if! + q + p + 1 is even, then

[a() a1ikQ l l l ae+q+p+1]

is a solution to P,. (In the above, we write & to denote the string obtained

from ai with each symbol a in ar; replaced by the symbol 7i.)