or
a 1 a 2 …a k-1 qa k a k+1 …a n
is the instantaneous description of a machine in state q with the tape depicted in
Figure 9.6. The symbols a 1 ,…, a n show the tape contents, while q defines the
state of the control unit. This convention is chosen so that the position of the
read-write head is over the cell containing the symbol immediately following q.
Figure 9.6
The instantaneous description gives only a finite amount of information to
the right and left of the read-write head. The unspecified part of the tape is
assumed to contain all blanks; normally such blanks are irrelevant and are not
shown explicitly in the instantaneous description. If the position of blanks is
relevant to the discussion, however, the blank symbol may appear in the
instantaneous description. For example, the instantaneous description q ω
indicates that the read-write head is on the cell to the immediate left of the first
symbol of w and that this cell contains a blank.
Example 9.4
The pictures drawn in Figure 9.3 correspond to the sequence of instantaneous
descriptions q 0 aa, bq 0 a, bbq 0 , bq 1 b.
A move from one configuration to another will be denoted by . Thus, if
δ (q 1 , c)=(q 2 , e, R),
then the move
abq 1 cd abeq 2 d