Computability - Models of Computation: Exploring the Power of Computing - page 211

“Yes” “Yes”

Recognizer

Accepter
for L

(Decider)

w w

for L

“No”

(a) (b)

Figure 5.2 An accepter (a) for a language L is a Turing machine that can accept strings in a
language L but may not halt on all inputs. A decider or recognizer (b) for a language L is a Turing
machine that halts on all inputs and accepts strings in L .

The accepting halt state h has been singled out to emphasize language acceptance. How-
ever, there is nothing to prevent a TM from having multiple halt states, states from which it
does not exit. (A halt state can be realized by a state to which a TM returns on every input
without moving the tape head or changing the value under the head.) On the other hand, on
some inputs a TM may never halt. For example, it may endlessly move its tape head right one
cell and write the symbol a .
Notice that we do not require a TM M to halt on every input string for it to accept a
language L ( M ) . It need only halt on those strings in the language. A language L for which
there is a TM M accepting L = L ( M ) that halts on all inputs is decidable. The distinction
between accepting and recognizing (or deciding) a language L is illustrated schematically in
Fig. 5.2 . An accepter is a TM that accepts strings in L but may not halt on strings not in L .
When the accepter determines that the string w is in the language L ,itturnsonthe“Yes”
light. If this light is not turned on, it may be that the string is not in L or that the TM is just
slow. On the other hand, a recognizer or decider is a TM that halts on all inputs and accepts
strings in L . The “Yes” or “No” light is guaranteed to be turned on at some time.
The computing power of the TM is extended by allowing partial computations ,com-
putations on which the TM does not halt on every input. The computation of functions by
Turing machines is discussed in Section 5.9 .

5.1.1 Programming the Turing Machine
Programming a Turing machine means choosing a tape alphabet and designing its control
unit, a finite-state machine. Since the FSM has been extensively studied elsewhere, we limit
our discussion of programming of Turing machines to four examples, each of which illustrates
a fundamental point about Turing machines. Although TMs are generally designed to perform
unbounded computations, their control units have a bounded number of states. Thus, we must
insure that as they move across their tapes they do not accumulate an unbounded amount of
information.
A simple example of a TM is one that moves right until it encounters a blank, whereupon
it halts. The TM of Fig. 5.3 (a) performs this task. If the symbol under the head is 0 or 1,