Proof: A standard Turing machine can simulate a nondeterministic machine by
keeping track of all possible configurations, continually searching and updating
the entire active area. If k is the maximum branching factor for the
nondeterminism, then after n steps there are at most k n possible configurations.
Since at most one symbol can be added to each configuration by a single move,
the length of one configuration after n moves is O(n). Therefore, to simulate one
move, the standard machine must search an active area of length O(nk n ), leading
to the desired result. For some details, see Exercise 7 at the end of this section.
We must interpret this theorem carefully. It says that a nondeterministic
computation can always be performed on a deterministic machine if we are
willing to take into account an exponential increase in the time required. But this
conclusion comes from a particularly simple-minded simulation and one can still
hope to do better. The exploration of this issue is the core of complexity theory.
Example 12.7 suggests that algorithms for a multitape machine may be
closer to what we might use in practice than the cumbersome method for a
standard Turing machine. For this reason, we will use a multitape Turing
machine as our model for studying complexity issues, but as we will see, this is a
minor issue.
EXERCISES
For the exercises in this set, assume that the Turing machines involved are all
deterministic.
1. Find a linear-time algorithm for membership in {ww : w ∈ {a, b}*} using a
two-tape Turing machine. What is the best you could expect on a one-tape
machine?
2. Show that any computation that can be performed on a single-tape, off-line
Turing machine in time O (T(n)) also can be performed on a standard Turing
machine in time O (T(n)).
3. Show that any computation that can be performed on a standard Turing
machine in time O (T(n)) also can be performed on a Turing machine with
one semi-infinite tape in time O (T(n)).
4. Rewrite the boolean expression
keeping track of all possible configurations, continually searching and updating
the entire active area. If k is the maximum branching factor for the
nondeterminism, then after n steps there are at most k n possible configurations.
Since at most one symbol can be added to each configuration by a single move,
the length of one configuration after n moves is O(n). Therefore, to simulate one
move, the standard machine must search an active area of length O(nk n ), leading
to the desired result. For some details, see Exercise 7 at the end of this section.
We must interpret this theorem carefully. It says that a nondeterministic
computation can always be performed on a deterministic machine if we are
willing to take into account an exponential increase in the time required. But this
conclusion comes from a particularly simple-minded simulation and one can still
hope to do better. The exploration of this issue is the core of complexity theory.
Example 12.7 suggests that algorithms for a multitape machine may be
closer to what we might use in practice than the cumbersome method for a
standard Turing machine. For this reason, we will use a multitape Turing
machine as our model for studying complexity issues, but as we will see, this is a
minor issue.
EXERCISES
For the exercises in this set, assume that the Turing machines involved are all
deterministic.
1. Find a linear-time algorithm for membership in {ww : w ∈ {a, b}*} using a
two-tape Turing machine. What is the best you could expect on a one-tape
machine?
2. Show that any computation that can be performed on a single-tape, off-line
Turing machine in time O (T(n)) also can be performed on a standard Turing
machine in time O (T(n)).
3. Show that any computation that can be performed on a standard Turing
machine in time O (T(n)) also can be performed on a Turing machine with
one semi-infinite tape in time O (T(n)).
4. Rewrite the boolean expression