The only way to extend the partial solution is for the string from the A list to be a prefix of the remainder, gi01#. Thus, we must next choose the pair (QiO, Iga), which is one of those move-simulating pairs that we got from rule (3). The partial solution is thus:

A: # ,0

B: #?i01#lg2

We may now further extend the partial solution using the copying pairs from rule (2), until we get to the state in the second ID. The partial solution is then:

A: #gi01#l

B: #gi01#l92l#l

At this point, we can use another of the rule-(3) pairs to simulate a move; the appropriate pair is (galjOgi), and the resrdting partial solution is:

A: # i01#lg2l

B: #i01#lg2l#10gi

We now could use rule-(2) pairs to copy the next three symbols: #, 1, and 0. However, to go that far would be a mistake, since the next move of M moves the head left, and the 0 just before the state is needed in the next rule-(3) pair. Thus, we only copy the next two symbols, leaving partial solution:

A: #gi01#lg2l#l

B: #Qi01#l 2l#10gi#l

The appropriate rule-(3) pair to use is (0qi#, g201#), which gives us the partial solution:

A: #gi01#lg2l#10gi#

B: #gi01#lg2l#10gi#lg201#

Now, we may use another rule-(3) pair, (IgaOjgslO), which leads to acceptance:

A: #gi01#lg2l#10gi#lg20

B: #gi01#lg2l#109i#l?201#g3l0

At this point, we use pairs from rule (4) to eliminate all but дз from the ID, We also need pairs from rule (2) to copy symbols as necessary. The continuation of the partial solution is:

A: #9i01#lg2l#10gi#l(?201#<73l01#g301#g3l# Б: #(?101#1д21#10д1#1д201#дэ101#дз01#дз1#<?з#

With only 3 left in the ID, we can use the pair {дз##, #) from rule (5) to finish the solution:

A: #9i01#l92l#10gi#lg201#93l01#9301#?3l#g3## B: #gi01#lq2l#10g:#lg201#93l01#Q301#q3l#93##

□

Theorem 9.19: Posts Correspondence Problem is undecidable.

PROOF: We have almost completed the chain of reductions suggested by Fig. 9.11. The reduction of MPCP to PCP was shown in Theorem 9.17. The construction of this section shows how to reduce Lu to MPCP. Thus, we complete the proof of undecidabiiity of PCP by proving that the construction is correct, that is:

M accepts w if and only if the constructed MPCP instance has a solution.

(Only-lf) Example 9.18 gives the fundamental idea. If № is in i(M), then we can start with the pair from rule (1), and simulate the computation of M on w. We use a pair from rule (3) to copy the state from each ID and simulate one move of M, and we use the pairs from rule (2) to copy tape symbols and the marker # as needed. If M reaches an acceptuig state, then the pairs from rule (4) and a final use of the pair from rule (5) allow the A string to catch up to the В string and form a solution.

(If) We need to argue that tf the MPCP instance has a solution, it could only be because M accepts w. First, because we are dealing with MPCP, any solution must begin with the first pair, so a partial solution begins

A: #

B: #gow#

As long as there is no accepting state in the partial solution, the pairs from rules (4) and (5) are useless. States and one or two of their surrounding tape symbols ui an ID can only be handled by the pairs of rule (3), and all other tape symbols and # must be handled by pairs from rule (2). Thus, unless M reaches an accepting state, all partial solutions have the form

A: X B: xy

where x is a sequence of IDs of M representing a computation of M on input w, possibly followed by # and the beginning of the next ID a. The remainder у is the completion of a, another #, and the beginning of the ID that follows Qt, up to the point that x ended within a itself

In particular, as long as M does not enter an accepting state, the partial solution is not a solution; the В string is longer than the A string. Thus, if there is a solution, M must at some point enter an accepting state; i.e., M accepts w. □

9.4.4 Exercises for Section 9.4

Exercise 9.4.1: Tell whether each of the following instances of PCP has a solution. Each is presented as two lists A and B, and the ith strings on the two lists correspond for each г = 1,2,.. ..

*a) A = (01,001,10); S = (011,10,00).

b) A = (01,001,10); Л = (011,01,00).

c) A = {ab,a,bc,c)] В = {bc,ab,ca,a).

! Exercise 9.4.2: We showed that PCP was undecidable, but we assumed that the alphabet S could be arbitrary. Show that PCP is undecidable even if we limit the alphabet to S = {0,1} by reducing PCP to this special case of PCP.

*! Exercise 9.4.3: Suppose we limited PCP to a one-symbol alphabet, say E = {0}. Would this restricted case of PCP still be undecidable?

! Exercise 9.4.4: A Post tag system consists of a set of pairs of strings chosen from some finite alphabet S and a start string. If [w, x) is a pair, and у is any string over E, we say that wy \- yx. That is, on one move, we can remove some prefix w of the current string wy and instead add at the end the second component of a string x with which w is paired. Define Ь to mean zero or more steps of h, just as for derivations in a context-free grammar. Show that it is undecidable, given a set of pairs P and a start string z, whether z V- e. Hint: For each TM M and input ю, let z be the irutial ID of M with input m, followed by a separator symbol #. Select the pairs P such that any ID of M must eventually become the ID that follows by one move of M. If M enters an accepting state, arrange that the current string can eventually be erased, i,e., reduced to e,

9.5 Other Undecidable Problems

Now, we shall consider a variety of other problems that we can prove undecidable. The principal technique is reducing PCP to the problem we wish to prove undecidable.

9.5.1 Problems About Programs

Our first observation is that we can write a program, in any conventional language, that takes as input an instance of PCP and searches for solutions some systematic manner, e.g., in order of the length (number of pairs) of potential solutions. Since PCP allows arbitrary alphabets, we should encode the symbols of its alphabet in binary or some other fixed alphabet, as discussed in the box on PCP as a Language in Section 9.4.1,