For another example, consider what M does on the input 0010, which is not in the language accepted.

goOOlO h XqiOlO h XOgjlO Ь ХзОУО I- ЧаХОУО h XqoOYO h XXqiYO h XXYqO h XXYOqB

The behavior of M on 0010 resembles the behavior on 0011, until in ID XXYqO M scans the final 0 for the first time. M must move right, staying in state qi, which takes it to the ID XXYOqB. However, in state qi M has no move on tape symbol B; thus M dies and does not accept its input. □

8.2.4 Transition Diagrams for Turing Machines

We can represent the transitions of a Turing machine pictorially, much as we did for the PDA. A transition diagram consists of a set of nodes corresponding to the states of the TM. An arc from state q to state p is labeled by one or more items of the form X/YD, where X and Y are tape symbols, and D is a direction, either L or R. That is, whenever 5{q,X) = {p,Y,D), we find the label X/YD on the arc from q to p. However, in our diagrams, the direction D is represented pictorially by -f- for left and -> for right.

As for other kinds of transition diagrams, we represent the start state by the word Start and an arrow entering that state. Accepting states are indicated by double circles. Thus, the only information about the TM one cannot read directly from the diagram is the symbol used for the blank. We shall assume that symbol is В unless we state otherwise.

Example 8.3: Figure 8.10 shows the transition diagram for the Turing machine of Example 8.2, whose transition function was given in Fig. 8.9. □

Example 8.4: While today we find it most convenient to think of Turing machines as recognizers of languages, or equivalently, solvers of problems, Turings original view of his machine was as a computer of integer-valued functions. In his scheme, integers were represented in unary, as blocks of a single character, and the machine computed by changing the lengths of the blocks or by constructing new blocks elsewhere on the tape. In this simple example, we shall show how a Turing machine might compute the function -, which is called monus or proper subtraction and is defined Ъу m ~ n - max(m - n, 0). That is, m n is m - n if m > n and 0 if m < n.

A TM that performs this operation is specified by

М-({9о,91,-..,9б},{0,1}Л0Д.},<5.90,5)

Note that, since this TM is not used to accept inputs, we have omitted the seventh component, which is the set of accepting states. M will start with a tape consisting of 0 10 surrounded by blanks. M halts with 0 on its tape, surrounded by blanks.

Y/ Y-0/0-

Y/ Y 0/ 0

Start 0 /

1 / Y

X/ X-

YI Y-

BI В

YI Y

Figure 8.10; Transition diagram for a TM that accepts strings of the form 0 Г

M repeatedly finds its leftmost remaining 0 and replaces it by a blank. It then searches right, looking for a 1. After finding a 1, it continues right, until it comes to a 0, which it replaces by a 1. M then returns left, seeking the leftmost 0, which it identifies when it first meets a blank and then moves one cell to the right. The repetition ends if either:

1. Searching right for a 0, M encounters a blank. Then the n Os in ОЧО have all been changed to 1 s, and n + 1 of the ш Os have been changed to B. M replaces the n + 1 Is by one 0 and n Bs, leaving m. - n Os on the tape. Since m > n in this case, m - n = m - n.

2. Beginning the cycle, M cannot find a 0 to change to a blank, because the first m Os cdready have been changed to B. Then u > m, so m - n. - 0. M replaces all remaining Is and Os by Б and ends with a completely blank tape.

Figure 8.11 gives the rules of the transition function 6, and we have also represented 5 as a transition diagram in Fig. 8.12. The following is a summary of the role played by each of the seven states:

qo: This state begins the cycle, and also breaJks the cycle when appropriate. If M is scanning a 0, the cycle must repeat. The 0 is replaced by B, the head moves right, and state 51 is entered. On the other hand, if M is

Figure 8.11: A Turing machine that computes the proper-subtraction function

В/ В

Start

Figure 8.12: Transition diagram for the TM of Example 8.4