and M 2 accept the same language.
8. How is the conclusion of Exercise 7 affected if M 2 is a finite automaton?
9. Is the halting problem solvable for deterministic pushdown automata; that is,
given a pda as in Definition 7.3, can we always predict whether or not the
automaton will halt on input w?
10. Let M be any Turing machine and x and y two possible instantaneous
descriptions of it. Show that the problem of determining whether or not
is undecidable.
11. In Example 12.3, give the values of f (1) and f (2).
12. Show that the problem of determining whether a Turing machine halts on
any input is undecidable.
13. Let B be the set of all Turing machines that halt when started with a blank
tape. Show that this set is recursively enumerable, but not recursive.
14. Consider the set of all n-state Turing machines with tape alphabet Γ = {0,1,
}. Give an expression for m(n), the number of distinct Turing machines
with this Γ.
15. Let Γ= {0,1, } and let b(n) be the maximum number of tape cells
examined by any n-state Turing machine that halts when started with a
blank tape. Show that b (n) is not computable.
16. Determine whether or not the following statement is true: Any problem
whose domain is finite is decidable.
12.2 Undecidable Problems for Recursively
Enumerable Languages
We have determined that there is no membership algorithm for recursively
enumerable languages. The lack of an algorithm to decide on some property is
not an exceptional state of affairs for recursively enumerable languages, but