δ (q 1 ,a k ) = (q 2 ,b,L).
M is said to halt starting from some initial configuration x 1 q i x 2 if
for any q j and a, for which δ (q j ,a) is undefined. The sequence of configurations
leading to a halt state will be called a computation.
Example 9.3 shows the possibility that a Turing machine will never halt,
proceeding in an endless loop from which it cannot escape. This situation plays a
fundamental role in the discussion of Turing machines, so we use a special
notation for it. We will represent it by indicating that, starting from the initial
configuration x 1 qx 2 , the machine goes into a loop and never halts.
Turing Machines as Language Accepters
Turing machines can be viewed as accepters in the following sense. A string ω is
written on the tape, with blanks filling out the unused portions. The machine is
started in the initial state q 0 with the read-write head positioned on the leftmost
symbol of ω. If, after a sequence of moves, the Turing machine enters a final
state and halts, then w is considered to be accepted.
Definition 9.3
Let M= (Q,Σ,Γ,δ;q 0 , ,F) be a Turing machine. Then the language accepted by M
is