Строительный блокнот  Automata methods and madness 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 [ 131 ] 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175

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.



List A

List В

if5(g,X)-

(P,Y,R)

if5(g,X) =

lp,Y,Ly,

Z is any tape symbol

if%,B) =

(p,Y,R)

pZY#

if5(g,B) =

{р,у,ьу,

Z is any tape sjrmbol

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;



5(9 1)

6{quB)

(g2,o,L)

(92,1,Х)

(?ьО,Я)

(92,0, Л)

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.

Rule

List A

List В

Source

#9i01#

from S{qy, 0) -

(92,1,Я)

Ogil

92 00

from 6{q\, 1) -

(?2,0,L)

Igil

9210

from 6{qi, 1) =

(92,0,L)

091 #

9201#

from 6{qi,B) -

= (92,1,L)

l9i#

92ll#

from 5(91, B) -

--{Я2,1,Е)

O92O

9з00#

from 5(g2,0) -

{q3,0,L)

I92O

9з10#

from (5(92,0) =

(93,0,L)

from (92,1) -

(qiAR)

92 #

092#

from (5(92,B) =

= (92,0,Л)

O93O

O93I

I93O

I93I

93##

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#



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 [ 131 ] 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175