CS 332: Theory of Computation Prof. Mark Bun
Boston University October 27, 2021
Homework 7 – Due Tuesday, November 2, 2021 at 11:59 PM
Reminder Collaboration is permitted, but you must write the solutions by yourself without as-
sistance, and be ready to explain them orally to the course staff if asked. You must also identify
your collaborators and write “Collaborators: none” if you worked by yourself. Getting solutions from
outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Note You may use various generalizations of the Turing machine model we have seen in class, such as
TMs with two-way infinite tapes, stay-put, or multiple tapes. If you choose to use such a generalization,
state clearly and precisely what model you are using. You may describe Turing machines at a
high-level on this assignment.
Problems There are 4 required problems and 1 bonus problem.
1. (Uncountable sets)
(a) Aliens from the planet Fubar’d have (countably) infinite single-strand DNA sequences from the
set of nucleobases {A,C,G, T}. Let D be the set of all possible DNA sequences for residents
of Fubar’d, so D = {a1a2a3 · · · | ai ∈ {A,C,G, T}, i ∈ N}. Show that D is uncountable.
(b) A function f : N → N is increasing if f(i) < f(i + 1) for every i ∈ N. So f(1) = 1, f(2) = 4, f(3) = 9, . . . are the first few values of (what looks like) an increasing function f . But the function g where g(1) = 2, g(2) = 1, g(3) = 7, . . . is not increasing. Show that F = {f : N → N | f is increasing}, the set of all increasing functions, is uncountable. Hint: When you construct a function contradicting the diagonal, make sure that it is indeed a member of F , i.e., increasing. 2. (Reduction Mad-Libs) A language B ⊆ {y, z}∗ is sleepy if every string in B contains “zzz” as a substring. For example, the empty language, {zn | n ≥ 3}, and {ynzmyn | m ≥ 3, n ≥ 0} are all sleepy, but {y, yz, yzz, yzzz} and {zn | n ≥ 0} are not sleepy. The language STM = {⟨M⟩ | L(M) is sleepy} corresponds to the following computational problem: Given the encoding of a TM M , does M recognize a sleepy language? This exercise will walk you through a proof, by reduction, that STM is undecidable. Assume, for the sake of contradiction, that STM is decidable by a TM R. That is, there is a TM R that accepts ⟨M⟩ whenever L(M) is sleepy, and rejects ⟨M⟩ whenever L(M) is not sleepy. We will use R to construct a new TM T that decides the (undecidable) language ATM. Algorithm: T (⟨M,w⟩) Input : Encoding of a basic TM M over input alphabet {y, z}, string w ∈ {y, z}∗ 1. Construct the following TM N : N = “On input a string x ∈ {y, z}∗: If x ̸= zz, reject. Else, run M on input w. If it accepts, accept. Otherwise, reject.” 2. Run R on input ⟨N⟩. If it accepts, (i) . Otherwise, (ii) . 1 (a) This proof is by reduction from a language A to a language B. What are the languages A and B? (Make it clear in your solution which one is A and which one is B, since the order matters a lot!) (b) Consider the machine N constructed inside algorithm T . If M accepts on input w, what is the language L(N)? Is L(N) sleepy in this case? (c) If M does not accept on input w, what is the language L(N)? Is L(N) sleepy in this case? (d) Fill in the blanks labeled (i) and (ii) with accept or reject decisions to guarantee the following conditions: If M accepts input w, then T accepts input ⟨M,w⟩, and if M does not accept input w, then T rejects input ⟨M,w⟩. Use parts (a) and (b) to explain why these conditions hold for your choices of how to fill in the blanks. (Your job is done now, but you may want to keep reading to see the exciting conclusion of the proof.) By part (d), the TM M exactly decides the language ATM. But this language is undecidable, which is a contradiction. Hence our assumption that STM was decidable is false, so we conclude that STM is an undecidable language. 3. (Spooky TMs) A basic Turing machine M is spooky if there exists a string w ∈ {0, 1}∗ such that, on input w, the TM M has “1000” appear somewhere on its tape when run on input w.1 Consider the problem of determining whether (the encoding of) a TM M is spooky. (a) Formulate this problem as a language SPOOKYTM. Caution: The only input to this compu- tational problem is ⟨M⟩ for a TM M . This problem is closely related to, but for this reason different from, the language recognized by H in Discussion 7, Problem 2. Please make sure you understand how it’s different. (b) Prove that the language SPOOKYTM is undecidable. Hint: Give a reduction from the undecidable language ATM. That is, you should assume for the sake of contradiction that SPOOKYTM is decidable. Then under this assumption, construct a TM deciding ATM, explain why your decider is correct, and as a result conclude that your assumption that SPOOKYTM is decidable must have been false. It’s also fine if you want to give a reduction from a different undecidable language, instead, but your proof should still have this structure. (c) Is SPOOKYTM Turing-recognizable? Is SPOOKYTM Turing-recognizable? Give a convincing explanation for both of your answers, but a complete description of a TM or of a reduction is not necessary. 4. (Subset detection) Consider the following computational problem: Given the (encodings of) two basic TMs M and N , determine whether the language recognized by M is a subset of the language recognized by N . (a) Formulate this problem as a language SUBSETTM. (b) Prove that the language SUBSETTM is undecidable. 5. (Bonus problem) Define the language XORTM = {⟨M,w, v⟩ | M is a TM that accepts exactly one of the strings w, v}. Prove that both XORTM and its complement XORTM are both unrecog- nizable. 1The string “1000” is supposed to look kind of like “boo.” Happy Halloween! 2