This definition indicates that the input w is written on the tape with blanks on
either side. The reason for excluding blanks from the input now becomes clear:
It assures us that all the input is restricted to a well-defined region of the tape,
bracketed by blanks on the right and left. Without this convention, the machine
could not limit the region in which it must look for the input; no matter how
many blanks it saw, it could never be sure that there was not some nonblank
input somewhere else on the tape.
Definition 9.3 tells us what must happen when w ∈ Γ L (M). It says nothing
about the outcome for any other input. When w is not in L (M), one of two things
can happen: The machine can halt in a nonfinal state or it can enter an infinite
loop and never halt. Any string for which M does not halt is by definition not in
L(M).
Example 9.6
For Σ = {0,1}, design a Turing machine that accepts the language denoted by the
regular expression 00 * .
This is an easy exercise in Turing machine programming. Starting at the left
end of the input, we read each symbol and check that it is a 0. If it is, we
continue by moving right. If we reach a blank without encountering anything but
0, we terminate and accept the string. If the input contains a 1 anywhere, the
string is not in L(00 * ), and we halt in a nonfinal state. To keep track of the
computation, two internal states Q= {q 0 ,q 1 }and one final state F= {q 1 } are
sufficient. As transition function we can take As long as a 0 appears under the
read-write head, the head will move to the right. If at any time a 1 is read, the
machine will halt in the nonfinal state q 0 , since δ(q 0 ,1) is undefined. Note that
the Turing machine also halts in a final state if started in state q 0 on a blank. We
could interpret this as acceptance of λ, but for technical reasons the empty string
is not included in Definition 9.3.
The recognition of more complicated languages is more difficult. Since
Turing machines have a primitive instruction set, the computations that we can
program easily in a higher-level language are often cumbersome on a Turing
either side. The reason for excluding blanks from the input now becomes clear:
It assures us that all the input is restricted to a well-defined region of the tape,
bracketed by blanks on the right and left. Without this convention, the machine
could not limit the region in which it must look for the input; no matter how
many blanks it saw, it could never be sure that there was not some nonblank
input somewhere else on the tape.
Definition 9.3 tells us what must happen when w ∈ Γ L (M). It says nothing
about the outcome for any other input. When w is not in L (M), one of two things
can happen: The machine can halt in a nonfinal state or it can enter an infinite
loop and never halt. Any string for which M does not halt is by definition not in
L(M).
Example 9.6
For Σ = {0,1}, design a Turing machine that accepts the language denoted by the
regular expression 00 * .
This is an easy exercise in Turing machine programming. Starting at the left
end of the input, we read each symbol and check that it is a 0. If it is, we
continue by moving right. If we reach a blank without encountering anything but
0, we terminate and accept the string. If the input contains a 1 anywhere, the
string is not in L(00 * ), and we halt in a nonfinal state. To keep track of the
computation, two internal states Q= {q 0 ,q 1 }and one final state F= {q 1 } are
sufficient. As transition function we can take As long as a 0 appears under the
read-write head, the head will move to the right. If at any time a 1 is read, the
machine will halt in the nonfinal state q 0 , since δ(q 0 ,1) is undefined. Note that
the Turing machine also halts in a final state if started in state q 0 on a blank. We
could interpret this as acceptance of λ, but for technical reasons the empty string
is not included in Definition 9.3.
The recognition of more complicated languages is more difficult. Since
Turing machines have a primitive instruction set, the computations that we can
program easily in a higher-level language are often cumbersome on a Turing