is made whenever the internal state is q 1 , the tape contains abcd, and the readwrite head is on the c. The symbol has the usual meaning of an arbitrary
number of moves. Subscripts, such as
are used in arguments to distinguish
between several machines.
Example 9.5
The action of the Turing machine in Figure 9.3 can be represented by
or
For further discussion, it is convenient to summarize the various
observations just made in a formal way.
Definition 9.2
Let M= (Q, Σ,Γ,δ,q 0 ,, ,F) be a Turing machine. Then any string a i …a k1 q 1 a k a k+1 …a n , with a i ∈ Γ and q 1 ∈ Q, is an instantaneous description of M. A
move
is possible if and only if
δ (q 1 ,a k ) = (q 2 ,b,R).
A move
is possible if and only if
number of moves. Subscripts, such as
are used in arguments to distinguish
between several machines.
Example 9.5
The action of the Turing machine in Figure 9.3 can be represented by
or
For further discussion, it is convenient to summarize the various
observations just made in a formal way.
Definition 9.2
Let M= (Q, Σ,Γ,δ,q 0 ,, ,F) be a Turing machine. Then any string a i …a k1 q 1 a k a k+1 …a n , with a i ∈ Γ and q 1 ∈ Q, is an instantaneous description of M. A
move
is possible if and only if
δ (q 1 ,a k ) = (q 2 ,b,R).
A move
is possible if and only if