CS 332: Theory of Computation Prof. Mark Bun
Boston University March 15, 2021
Homework 6 – Due *Friday*, March 19, 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.
Problems There are 5 required problems and 1 bonus problem.
1. (Code as data) Consider the following description of a three-tape TM H.
Algorithm: H(〈M,w〉)
Input : Encoding of a basic TM M and a string w ∈ {0, 1}∗
1. Copy the the string w to tape 2.
2. Repeat the following three steps forever:
3. Simulate M for one step on tape 2.
4. Erase the contents of tape 3. Copy the contents of tape 2 to tape 3, and check if the
substring “1010” appears on tape 3. If it does, accept. Otherwise, continue.
5. If M halts (in either an accept or reject state), reject. Otherwise, continue.
(a) Let M1 be the following (uninteresting) TM. Is 〈M1, ε〉 ∈ L(H)? Explain why or why not.
Algorithm: M1(x)
Input : String x ∈ {0, 1}∗
1. Write “010101” to the tape and reject.
(b) Let M2 be the following TM. Is 〈M2, 101〉 ∈ L(H)? Explain why or why not.
Algorithm: M2(x)
Input : String x ∈ {0, 1}∗
1. Scan the input string x and (without writing anything) accept if the last symbol of x is 1.
Otherwise, reject.
(c) What is the language L(H) recognized by H?
(d) Is H a decider for the language L(H)? Explain why or why not.
1
2. (Countable sets)
(a) Whitespace (https://en.wikipedia.org/wiki/Whitespace_(programming_language)) is
a programming language in which valid programs consist only of spaces (S), tabs (T), and
linebreaks (L). Show that the set W of all (finite) Whitespace programs is countable. (For
the sake of readability, you can use the symbols S,T, L to stand for legal Whitespace characters
in your proof.)
(b) Show that if S and T are countable sets, then their union S ∪ T is also countable.
3. (Uncountable sets)
(a) A game of Tetris is an infinite sequence of “tetrominos” which can have one of seven types
1, . . . , 7. For example, a Tetris game may look like (7, 1, 4, 2, 2, . . . ). Use a proof by diagonal-
ization to show that the set T of all Tetris games is uncountable.
(b) An infinite sequence (x1, x2, x3, . . . ) is collision-free if no number appears more than once in
that sequence. For example, (1, 5, 2, 5, . . . ) is not collision-free because 5 appears at least twice.
Use a proof by diagonalization to show that the set C of all collision-free infinite sequences of
natural numbers is uncountable.
Hint: When you construct a sequence contradicting the diagonal, make sure that it is indeed
a member of C.
4. (Reduction Mad-Libs) A language B is excited if every string in B takes the form ww for some
w ∈ {0, 1}∗. For example, {00, 1111, 1010} is excited, but {00, 10} is not excited. The language
EXTM = {〈M〉 | L(M) is excited} corresponds to the following computational problem: Given the
encoding of a TM M , does M recognize an excited language? This exercise will walk you through
a proof, by reduction, that EXTM is undecidable.
Assume, for the sake of contradiction, that EXTM is decidable by a TM R. That is, there is a TM
R that accepts 〈M〉 whenever L(M) is excited, and rejects 〈M〉 whenever L(M) is not excited. We
will use R to construct a new TM S that decides the (undecidable) language ATM.
Algorithm: S(〈M,w〉)
Input : Encoding of a basic TM M over input alphabet {0, 1}, string w ∈ {0, 1}∗
1. Construct the following TM N :
N = “On input a string x ∈ {0, 1}∗:
If x = 00, accept.
Else, run M on input w. If it accepts, accept. Otherwise, reject.”
2. Run R on input 〈N〉. If it accepts, (i) . Otherwise, (ii) .
(a) Consider the machine N constructed inside algorithm S. If M accepts on input w, what is
the language L(N)? Is L(N) excited in this case?
(b) If M does not accept on input w, what is the language L(N)? Is L(N) excited in this case?
(c) Fill in the blanks labeled (i) and (ii) with accept or reject decisions to guarantee the following
conditions: If M accepts input w, then S accepts input 〈M,w〉, and if M does not accept
input w, then S 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.
2
https://en.wikipedia.org/wiki/Whitespace_(programming_language)
(Your job is done now, but you may want to keep reading to see how the proof concludes.) By
part (c), the TM M exactly decides the language ATM. But this language is undecidable, which
is a contradiction. Hence our assumption that EXTM was decidable is false, so we conclude that
EXTM is an undecidable language.
5. (Unary acceptance) A Turing machine M accepts a unary string if there exists a string x ∈ {1}∗
such that M accepts on input x. Consider the problem of determining whether (the encoding of)
a TM M accepts a unary string.
(a) Formulate this problem as a language UA. Caution: The only input to this computational
problem is 〈M〉 for a TM M .
(b) Consider the following “first attempt” at designing a TM N recognizing the language UA.
Algorithm: N(〈M〉)
Input : Encoding of a basic TM M over input alphabet {0, 1}
1. Let xn = 1
n. For each n = 0, 1, 2, 3, . . . :
2. Run M on input xn. If it accepts, accept. Otherwise, continue.
Explain why N fails to recognize UA.
(c) Design and analyze a Turing machine that does recognize the language UA. Hint: Solved
exercise 4.5 in Sipser illustrates the “dovetailing” trick that will be useful here.
(d) Prove that the language UA is undecidable.
Hint: Give a reduction from the undecidable language ATM. That is, you should assume for
the sake of contradiction that UA is decidable. Then under this assumption, construct a TM
deciding ATM, prove that this decider is correct, and as a result conclude that your assumption
that UA is decidable must have been false.
6. (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 unrecognizable.
3