the tape either
xx…110xx…x
or
xx…xx0xx…x11
depending on whether x > y or y > x. In the first case, when we attempt to match
another 1, we encounter the blank at the right of the working space. This can be
used as a signal to enter the state q y . In the second case, we still find a 1 on the
right when all 1’s on the left have been replaced. We use this to get into the other
state q n . The complete program for this is straightforward and is left as an
exercise.
This example makes the important point that a Turing machine can be
programmed to make decisions based on arithmetic comparisons. This kind of
simple decision is common in the machine language of computers, where
alternate instruction streams are entered, depending on the outcome of an
arithmetic operation.
EXERCISES
** 1. Write a Turing machine simulator in some higher-level programming
language. Such a simulator should accept as input the description of any
Turing machine, together with an initial configuration, and should produce as
output the result of the computation.
2. Design a Turing machine with no more than three states that accepts the
language L(a (a + b)*). Assume that Σ = {a,b}. Is it possible to do this with a
two-state machine?
3. Determine what the Turing machine in Example 9.7 does when presented
with the inputs aba and aaabbbb.
4. Is there any input for which the Turing machine in Example 9.7 goes into an
infinite loop?
5. What language is accepted by the Turing machine whose transition graph is
xx…110xx…x
or
xx…xx0xx…x11
depending on whether x > y or y > x. In the first case, when we attempt to match
another 1, we encounter the blank at the right of the working space. This can be
used as a signal to enter the state q y . In the second case, we still find a 1 on the
right when all 1’s on the left have been replaced. We use this to get into the other
state q n . The complete program for this is straightforward and is left as an
exercise.
This example makes the important point that a Turing machine can be
programmed to make decisions based on arithmetic comparisons. This kind of
simple decision is common in the machine language of computers, where
alternate instruction streams are entered, depending on the outcome of an
arithmetic operation.
EXERCISES
** 1. Write a Turing machine simulator in some higher-level programming
language. Such a simulator should accept as input the description of any
Turing machine, together with an initial configuration, and should produce as
output the result of the computation.
2. Design a Turing machine with no more than three states that accepts the
language L(a (a + b)*). Assume that Σ = {a,b}. Is it possible to do this with a
two-state machine?
3. Determine what the Turing machine in Example 9.7 does when presented
with the inputs aba and aaabbbb.
4. Is there any input for which the Turing machine in Example 9.7 goes into an
infinite loop?
5. What language is accepted by the Turing machine whose transition graph is