transition function δ defines howthis computer acts, and we often call it the
“program” of the machine.
As always, the automaton starts in the given initial state with some
information on the tape. It then goes through a sequence of steps controlled by
the transition function δ. During this process, the contents of any cell on the tape
may be examined and changed many times. Eventually, the whole process may
terminate, which we achieve in a Turing machine by putting it into a halt state.
A Turing machine is said to halt whenever it reaches a configuration for which δ
is not defined; this is possible because δ is a partial function. In fact, we will
assume that no transitions are defined for any final state, so the Turing machine
will halt whenever it enters a final state.
Example 9.2
Consider the Turing machine defined by
Q = {q 0 , q 1 },
Σ = {a, b},
Γ = {a, b, },
F= {q 1 },
and
δ (q 0 , a)= (q 0 , b, R),
δ (q 0 , b)= (q 0 , b, R),
δ (q 0 , )= (q 1 , , L),
If this Turing machine is started in state q 0 with the symbol a under the readwrite head, the applicable transition rule is δ (q 0 ,a)= (q 0 ,b,R). Therefore, the
read-write head will replace the a with a b, then move right on the tape. The
machine will remain in state q 0 . Any subsequent a will also be replaced with a b,
but b's will not be modified. When the machine encounters the first blank, it will