EXERCISES
1. Describe in detail how H in Theorem 12.1 can be modified to produce H’.
2. Suppose we change Definition 12.1 to require that
or
q n w, depending on whether M applied to w halts or not. Reexamine
the proof of Theorem 12.1 to show that this difference in the definition does
not affect the proof in any significant way.
3. Show that the following problem is undecidable. Given any Turing machine
M, a ∈ Γ, and w ∈ Σ + , determine whether or not the symbol a is ever written
when M is applied to w.
4. In the general halting problem, we ask for an algorithm that gives the correct
answer for any M and w. We can relax this generality, for example, by
looking for an algorithm that works for all M but only a single w. We say that
such a problem is decidable if for every w there exists a (possibly different)
algorithm that determines whether or not (M,w) halts. Show that even in this
restricted setting the problem is undecidable.
5. Show that there is no algorithm to decide whether or not an arbitrary Turing
machine halts on all input.
6. Consider the question: “Does a Turing machine in the course of a
computation revisit the starting cell (i.e., the cell under the read-write head at
the beginning of the computation)?” Is this a decidable question?
7. Show that there is no algorithm for deciding if any two Turing machines M 1
1. Describe in detail how H in Theorem 12.1 can be modified to produce H’.
2. Suppose we change Definition 12.1 to require that
or
q n w, depending on whether M applied to w halts or not. Reexamine
the proof of Theorem 12.1 to show that this difference in the definition does
not affect the proof in any significant way.
3. Show that the following problem is undecidable. Given any Turing machine
M, a ∈ Γ, and w ∈ Σ + , determine whether or not the symbol a is ever written
when M is applied to w.
4. In the general halting problem, we ask for an algorithm that gives the correct
answer for any M and w. We can relax this generality, for example, by
looking for an algorithm that works for all M but only a single w. We say that
such a problem is decidable if for every w there exists a (possibly different)
algorithm that determines whether or not (M,w) halts. Show that even in this
restricted setting the problem is undecidable.
5. Show that there is no algorithm to decide whether or not an arbitrary Turing
machine halts on all input.
6. Consider the question: “Does a Turing machine in the course of a
computation revisit the starting cell (i.e., the cell under the read-write head at
the beginning of the computation)?” Is this a decidable question?
7. Show that there is no algorithm for deciding if any two Turing machines M 1