Г: The set of tape symbols is {B,*} x {0,1, c, B}. The first component, or tract:, can be either blanic or checked, represented by the symbols В and *, respectively. We use the * to check off symbols of the first and second groups of Os and Is, eventually confirming that the string to the left of the center marker с is the same as the string to its right. The second component of the tape symbol is what we think of as the tape symbol itself. That is, we may think of the symbol [B,X] as if it were the tape symbol X, for X - 0,1, c, B.

S: The input symbols are [B, 0] and [B,l], which, as just mentioned, we identify with 0 and 1, respectively.

6: The transition fimction S is defined by the following rules, in which a and b each may stand for either 0 or 1.

1. S{[qi,B},[B,a]) - {[q2,a],[*,a],R}. In the initial state, M picks up the symbol a (which can be either 0 or 1), stores it in its finite control, goes to control state 92, checks off the symbol it just scanned, and moves right. Notice that by changing the first component of the tape symbol from В to *, it performs the check-off.

2. 6{[q2,a],[B,b]) = {[q2,a],[B,b],R). M moves right, looking for the symbol c. Remember that a and b can each be either 0 or 1, independently, but cannot be c.

3. 6{lq2,a],[B,c]) = {[дз,а], [В, c],R). When M finds the c, it continues to move right, but changes to control state 93.

4. 6([q3,a],[*,b]) = {[q3,a],[*,b].,R). In state 93, M continues past all checked symbols.

5. 6{[q3,a],[B,a]) - ([94,-6], [*,a],L). If the first unchecked symbol that M finds is the same as the symbol in its finite control, it checks this symbol, because it has matched the corresponding symbol from the first block of Os and Is. M goes to control state 94, dropping the symbol from its finite control, and starts moving left.

6. 6{[qi,B],[*,a]) = {[q4,B],[*,a],L). M moves left over checked symbols.

7. S{[q4,B],[B,c]) = i[g5,B],[B,c],L). When M encounters the symbol c, it switches to state and continues left. In state 95, M must make a decision, depending on whether or not the symbol immediately to the left of the с is checked or unchecked. If checked, then we have already considered the entire first block of Os and Is - those to the left of the c. We must make sure that all the Os and Is to the right of the с are also checked, and accept if no unchecked symbols remain to the right of the c. If the symbol immediately to the left of the с is unchecked, we find the leftmost unchecked symbol, pick it up, and start the cycle that began in state qi.

8.3.3 Subroutines

As with programs in general, it helps to think of Turuig machines as built from a collection of interacting components, or subroutines. A Turing-machine Subroutine is a set of states that perform some useful process. This set of states includes a start state and another state that temporarily has no moves, and that serves as the return state to pass control to whatever other set of states called the subroutine. The call of a subroutine occurs whenever there is a transition to its initial state. Since the TM has no mechanism for remembering a return address, that is, a state to go to after it finishes, should our design of a TM call for one subroutine to be called from several states, we can make copies of the subroutine, using a new set of states for each copy. The calls are made to the start states of different copies of the subroutine, and each copy returns to a different state.

Example 8.8: We shall design a TM to implement the function multiplication. That is, our TM will start with 0 10 1 on its tape, and will end with 0 * on the tape. An outline of the strategy is:

1. The tape will, in general, have one nonblank string of the form 010 10** for some k.

8. 5{[qs,B],[B,a]] = {[д,В],[В,а\,Ь). This branch covers the case where the symbol to the left of с is unchecked. M goes to state and continues left, looking for a checked symbol.

9, S{\qG,B],[B,a]) = ([qsjS],[B,a],L). As long as symbols are unchecked, M remains in state and proceeds left.

10. 5([ e,S],[*,a]) = ([g],B],[*,o],Л). When the checked symbol is found, M enters state gi and moves right to pick up the first unchecked symbol.

11. (S([g5,B],[*,o]) = {[q7,B],\*,a\,R). Now, let us pick up the branch from state 55 where we have just moved left from the с and fiird a checked symbol. We start moving right again, entering state 57.

12. 6{[q7,B\,[B,(\) = ([д8,Я],[Я,с],Л). In state q we shall surely see the c. We enter state q% as we do so, and proceed right.

13. (S{[g8,B],[*,e]) = ([gsjB], [*,o],ii). M moves right in state q&, skipping over any checked Os or Is that it finds.

14. 6{[qi,B],[B,B\) = {[qg,B\,[B,B\,R). If M reaches a blank cell is state $8 without encountering any unchecked 0 or 1, then M accepts. If M first finds an unchecked 0 or 1, then the blocks before and after the с do not match, and M halts without accepting.

□

2. In one basic step, we change a 0 in the first group to В and add n Os to the last group, giving us a string of the form 0 H0 10f+ .

3. As a result, we copy the group of n Os to the end m times, once each time we change a 0 in the first group to B. When the first group of Os is completely changed to blanks, there will be mn Os in the last group.

4. The final step is to change the leading 10 ! to blanks, and we are done.

The heart of this algorithm is a subroutine, which we call Copy. This subroutine implements step (2) above, copying the block of n Os to the end. More precisely. Copy converts an ID of the form 0 -=lgiO 10(* to ID O l(jf50 10* . Figure 8.14 shows the transitions of subroutine Copy. This subroutine marks the first 0 with an X, moves right in state 52 until it finds a blank, copies the 0 there, and moves left in state qz to find the marker X. It repeats this cycle until in state qi it finds a 1 instead of a 0. At that point, it uses state 94 to change the Xs back to Os, and ends in state 95.

The complete multiplication Turing machine starts in state go. The first thing it does is go, m several steps, from ID qoO 40 to ID 0 -lgi0 l. The transitions needed are shown in the portion of Fig. 8.15 to the left of the subroutine call; these transitions involve states go and ge only.

Then, to the right of the subroutine call in Fig. 8.15 we see states g? through gi2. The purpose of states qj, qe, and q is to take control after Copy has just copied a block of тг Os, and is in ID 0 -*l950 10* . Eventually, these states bring us to state goO ~*1040* . At that point, the cycle starts again, and Copy is called to copy the block of n Os again.

As an exception, in state ge the TM may find that all m Os have been changed to blanks (i.e., к = m). In that case, a transition to state дю occurs. This state, with the help of state (/n, changes the leading 10 1 to blanks and enters the halting state giy. At this point, the TM is in ID qi20, and its job is done. □

8.3.4 Exercises for Section 8.3

! Exercise 8.3.1; Rjedesign your Turing machines fi:om Exercise 8.2.2 to take advantage of the programming techniques discussed in Section 8.3.

! Exercise 8.3.2: A common operation m Turing-machine programs involves shifting over. Ideally, we would like to create an extra cell at the currevJ head position, in which we could store some character. However, we cannot edit the tape in this way. Rather, we need to move the contents of each of the cells to the right of the current head position one cell right, and then find our way hack to the current head position. Show how to perform this operation. Hint: Leave a special symbol to mark the position to which the head must return.