8.2.3 Instantaneous Descriptions for Turing Machines

In order to describe formally what a Turing machine does, we need to develop a notation for configurations or instantaneous descriptions (IDs), lilce the notation we developed for PDAs. Since a TM, in principle, has an infinitely long tape, we might imagine that it is impossible to describe the configurations of a TM succinctly. However, after any finite number of moves, the TM can have visited only a finite number of cells, even though the number of cells visited can eventually grow beyond any finite limit. Thus, in every ID, there is an infinite prefix and an infinite suffix of cells that have never been visited. These cells must all hold either blanks or one of the finite number of input symbols. We thus show in an ID only the cells between the leftmost and the rightmost non-blanks. Under special conditions, when the head is scanning one of the leading or trailing blanks, a finite number of blanks to the left or right of the nonblank portion of the tape must also be included in the ID.

In addition to representing the tape, we must represent the finite control and the tape-head position. To do so, we embed the state in the tape, and place it immediately to the left of the cell scanned. To disambiguate the tape-plus-state string, we have to make sure that we do not use as a state any symbol that is also a tape symbol. However, it is easy to change the names of the states so they have nothing in common with the tape symbols, since the operation of the TM does not depend on what the states are called. Thus, we shall use the string X1X2 Xi-i gXiXi+i Xn to represent an ID in which

1. g is the state of the Turing machine.

2. The tape head is scanning the ith symbol from the left.

3. XiX2-- Xn is the portion of the tape between the leftmost and the rightmost nonblank. As an exception, if the head is to the left of the leftmost nonblank or to the right of the rightmost nonblank, then some prefix or suffix of ATi X2 Xn will be blank, and i will be 1 or n, respectively.

We describe moves of a Turing machine M - {Q, S, Г, 6, qo,B, F) by the h

notation that was used for PDAs. When the TM M is understood, we shall

use just Ь to reflect moves. As usual, h , or just h , will be used to indicate

zero, one, or more moves of the TM M.

Suppose 5{q, Xi) - {p, Y, L)\ i.e., the next move is leftward. Then

X1X2 Xi\qXiXi+i -X h XiXj Xi-2pXi-iYXi+i - Xn

Notice how this move reflects the change to state p and the fact that the tape head is now positioned at cell г - 1. There are two important exceptions:

1. If г = 1, then M moves to the blank to the left of Xj. In that case,

дХгХ2---Хп h pBYX2-Xn

2. If i - 71 and Y = Б, then the synnbol В written over X joins the infinite sequence of traiUng blanks and does not appear in the next ID. Thus,

XiX2---Xn-iQX \- XiX2---Xn-2pXn-\

Now, suppose d{q,Xi) = {p,Y,R); i.e., the next move is rightward. Then X],X2 Xi-iqXiXi.1 X I- XiX2 - Xi-iYpXi+\ -Xn

Here, the move reflects the fact that the head has moved to cell г + 1. Again there are two important exceptions:

1. If i = n, then the г + 1st cell holds a blank, aud that cell was not part of the previous ID. Thus, we instead have

X,X2 X .iqX h XiX-2 XniYpB

2. If г = 1 and Y = B, then the symbol В written over ATi joins the infinite sequence of leading blanks and does not appear in the next ID. Thus,

qXiX2---X\- pX2--X

Example Й.2: Let us design a Tiiring machine and see how it behaves on a typical input. The TM we construct will accept the language {0 1 n > 1}. Liitially, it is given a finite sequence of Os and Is on its tape, preceded and followed by an infinity of blanks. Alternately, the TM wiU change a 0 to an X and then a 1 to a У, until all Os and Is have been matched.

In more detail, starting at the left end of the input, it repeatedly changes a 0 to an X and moves to the right over whatever Os and Ks it sees, until it comes to a 1. It changes the 1 to a F, and moves left, over Ks and Os, until it finds an X. At that point, it looks for a 0 immediately to the right, and if it finds one, changes it to X and repeats the process, changing a matching 1 to a Y.

If the nonblank input is not in 0*1*, then the TM will eventually fail to have a next move and will die without accepting. However, if it finishes changing all the Os to Xs on the same round it changes the last 1 to a У, then it has found its input to be of the form ОЧ and accepts. The formal specification of the TM M is

M = {{qo, qi, 92,93, ?4}, {0,1}, {0,1, X, Y, B}, 6, qo, B, {q})

where 6 is given by the table in Fig. 8.9.

As M performs its computation, the portion of the tape, where Afs tape head has visited, will always be a sequence of symbols described by the regular expression X0*Y*1*. That is, there will be some Os that have been changed

Figure 8.9: A Turing machine to accept {0*4 n > 1}

to Xs, followed by some Os that have not yet been changed to Xs. Then there are some Is that were changed to Vs, and Is that have not yet been changed to Ys. There may or may not be some Os and Is following.

State is the initial state, and M also enters state Qq every time it returns to the leftmost remaining 0. If M is in state go and scanning a 0, the rule in the upper-left corner of Fig. 8.9 tells it to go to state , change the 0 to an X, and move right. Once in state 91, M keeps moving right over all Os and Ys that it finds on the tape, remaining in state qi- ИМ sees an X or a B, it dies. However, if M sees a 1 when in state , it changes that 1 to a У, enters state 92) and starts moving left.

In state ?2, M moves left over Os and Ys, remaining in state 92- When M reaches the rightmost X, which marks the right end of the block of Os that have already been changed to X, M returns to state qo and moves right. There are two cases:

1. If M now sees a 0, then it repeats the matching cycle we have just described.

2. If M sees a Y, then it has changed all the Os to Xs. If all the Is have been changed to Ys, then the input was of the form 0 1 , and M should accept. Thus, M enters state qs, and starts moving right, over Уз. If the first symbol other than a Y that M sees is a blank, then indeed there were an equal number of Os and Is, so M enters state 94 and accepts. On the other hand, if M encounters another 1, then there are too many Is, so M dies without accepting. If it encounters a 0, then the input was of the wrong form, and M also dies.

Here is an example of an accepting computation by M. Its input is 0011. Initially, M is in state qo, scanning the first 0, i.e., Ms initial ID is qoOOll. The entire sequence of moves of M is:

goOOll 1- XqiOn h XOill h ХгОП h 92ХОУ1 h XgoOri h XXgiyi h XXYqi 1 h XXqiYY h XqXYY h XXqoYY t- XXYqsY h XXYYqB h XXYYBqB