The essential idea is that MPCP instance (A,B) simulates, in its partial solutions, the computation of M on input w. That is, partial solutions will consist of strings that are prefixes of the sequence of IDs of M: #ai #а2#аз# , where 1 is the initial ID of M with input w, and h Ofi+i for all г. The string from the В list will always be one ID ahead of the string from the A list, unless M enters an accepting state. In that case, there will be pairs to use that will allow the A list to catch up to the В list cind eventually produce a solution. However, without entering an accepting state, there is no way that these pairs can be used, and no solution exists.

To simplify the construction of an MPCP histance, we shall invoke Theorem 8.12, which says that we may assume our TM never prints a blank, and never moves left from its initial head position. In that case, an ID of the Turing machine will always be a string of the form aq, where q and 0 are strings of nonblank tape symbols, and g is a state. However, we shall allow to be empty if the head is at the blank immediately to the right of a, rather than placing a blank to the right of the state. Thus, the symbols of a and 0 will correspond exactly to the contents of the cells that held the input, plus any cells to the right that the head has previously visited.

Let M = {Q,i:,r,S,qo,B,F) be a TM satisfying Theorem 8.12, and let w in E* be an input string. We construct an instance of MPCP as follows. To understand the motivation behind our choice of pairs, remember that the goal is for the first list to be one ID behind the second list, unless M accepts.

1. The first pair is:

List A List В

This, pair, which must start гту solution according to the rules of MPCP, begins the simulation of M on input w. Notice that initially, the В list is a complete ID ahead of the A fist.

2, Tape symbols and the separator # can be appended to both Hsts. The pairs

List A List В

X X for each X in Г # #

allow symbols not involving the state to be copied. In effect, choice of these pairs lets us extend the A string to match the В string, and at the same time copy parts of the previous ID to the end of the В string. So doing helps to form the next ID in the sequence of moves of M, at the end of the В string.

Like the pairs of (2), these pairs help extend the В string to add the next ID, by extending the A string to match the В string. However, these pairs use the state to determine the change in the current ID that is needed to produce the next ID. These changes - a new state, tape symbol, and head move - are reflected in the ID beuig constructed at the end of the В string.

4. If the ID at the end of the Б string has an accepting state, then we need to allow the partial solution to become a complete solution. We do so by extending with IDs that are not really IDs of M, but represent what would happen if the accepting state were allowed to consume all the tape symbols to either side of it. Thus, if q is an accepting state, then for all tape symbols X and F, there are pairs:

List A List В XqY q Xq q qY q

5. Finally, once the accepting state has consumed all tape symbols, it stands alone as the last ID on the В string. That is, the remainder of the two strings (the sufiix of the В string that must be appended to the A string to match the Б string) is We use the final pair:

List A List В

g## #

to complete the solution.

In what follows, we refer to the five kinds of pairs generated above as the pairs firom rule (1), rule (2), and so on.

Example 9.18: Let us convert the TM

M = {{qi,q-2,q3}dG},{<i>B}A<h,B,{q}) where 6 is given by:

3. To simulate a move of M, we have certain pairs that reflect those moves. For all q iaQ - F (i.e., is a nonaccepting state), p in Q, and X, У, and Z in Г we have;

and input string ui = 01 to an instance of MPCP. To simplify, notice that M never writes a blank, so we shall never have В in an ID. Thus, we shall omit all the pairs that involve B. The entire list of pairs is in Fig. 9.15, along with explanations about where each pair comes from.

Figure 9.15: MPCP instance constructed from TM M of Example 9.18

Note that M accepts the input 01 by the sequence of moves

giOl Ь 1211- IO91 h IgaOl h дз101

Let us see the sequence of partial solutions that mimics this computation of M and eventually leads to a solution. We must start with the first pair, as required in any solution to MPCP:

A: #

B: #9i01#