CSC173: Homework 3.2
Turing Machines and Decidability
1. Answer the following questions about Turing machines. Explain your answers very briefly.
(a) Can a Turing machine ever write the blank symbol on its tape?
(b) Can the tape alphabet Γ be the same as the input alphabet Σ ?
(c) Can a Turing machine’s head ever be in the same location on two successive steps?
(d) Can a Turing machine contain just a single state?
2. We proved that a language is recognized by a Turing machine if and only if some enumerator enumerates it (Sipser Theorem 3.21). Does the following simpler sim- ulation algorithm work for the proof? Why or why not?
(a) Repeat for i = 1, 2, . . . :
(b) Run M on the ith possible input string
(c) If it accepts, print out that string
3. Prove that the language L = {an bn cn |n ≥ 0} is recursive (decidable).
4. Prove that if a language L is decidable (recursive), then it is also recognizable (recursively enumerable).
5. Prove that if L is a decidable (recursive) language, then its complement, L, is also decidable (recursive).
6. Prove that any finite language is decidable (recursive).
7. Let A be the language containing only the single string s where
Assume that the question of whether life will be found on Mars has an unambigu- ous “yes” or “no” answer. Is A decidable (recursive)? Why or why not?