CS 332: Theory of Computation Professor Mark Bun Boston University March 23, 2020
Homework 6 – Due Monday, March 30, 2020 before 2:00PM
Reminder Collaboration is permitted, but you must write the solutions by yourself without assistance, and be ready to explain them orally to the course staff if asked. You must also identify your collaborators. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Exercises Please practice on the following exercises and solved problems in Chapter 5: 5.1, 5.2, 5.4–5.7, 5.10, 5.11. The material they cover may appear on exams.
Note If you need to describe a Turing machine, please give a high-level description as in Chapter 4.1 of Sipser or in Lecture 13.
Problems There are 3 mandatory problems and one bonus problem.
1. (Adding TM) A TM correctly adds if, given two binary numbers, separated by #, it halts with their sum (in binary) on its tape. (It does not matter what it does on other inputs.) Consider the problem of determining whether a TM correctly adds. Formulate this problem as a language and prove it is undecidable.
2. (Enthusiastic TM) Consider the problem of determining whether a given TM ever1 writes “332” on three adjacent squares of its tape. You may assume that the input alphabet of this TM is {0,1} and the tape alphabet is {0,1,2,…,9}.
(a) Formulate this problem as a language ENTHUSIASTICTM. (b) Show ENTHUSIASTICTM is undecidable.
(c) Prove that ENTHUSIASTICTM is Turing-recognizable.
(d) Is ENTHUSIASTICTM Turing-recognizable? Prove or disprove.
3. (Recognizable and unrecognizable languages)
(a) (Complement of ALLCFG) Let ALLCFG = {⟨G⟩ | G is a CFG with terminal set Σ and L(G) =
Σ∗}. Prove that the complement of ALLCFG is Turing-recognizable.
(b) (Accepting its own description) Consider the self-acceptance problem for Turing ma- chines described in Lecture 15: SATM = {⟨M⟩ | M is a TM that accepts on input ⟨M⟩}. Modify the diagonalization proof of undecidability for SATM to show that SATM is not even Turing-recognizable (i.e., SATM is not co-Turing-recognizable).
1on some input
1
(c) (DECIDERTM) Let DECIDERTM = {⟨M⟩| M is a TM that halts on every input}. Prove the following statements.
i. DECIDERTM is not Turing-recognizable (i.e., DECIDERTM is not co-Turing-recognizable). ii. DECIDERTM is not Turing-recognizable.
4∗ (Bonus, no collaboration is allowed) Let A be a Turing-recognizable language consisting of descriptions of Turing machines, {⟨M1⟩, ⟨M2⟩, …}, where every Mi is a decider. Prove that some decidable language D is not decided by any decider Mi whose description appears in A. (Hint: Use diagonalization and consider an enumerator for A.)
2