Description
1. [10 marks] We begin with some mathematics regarding uncountability. Let N = {0, 1, 2, 3, . . .} denote the set
of natural numbers.
(a) [5 marks] Prove that the set of integers Z = {. . . , −3, −2, −1, 0, 1, 2, 3 . . .} has the same size as N by
giving a bijection between Z and N.
(b) [5 marks] Let B denote the set of all infinite sequences over {0, 1}. Show that B is uncountable using a
proof by diagonalization.
2. [9 marks] We next move to a warmup question regarding reductions.
(a) [2 marks] Intuitively, what does the notation A ≤ B mean for problems A and B?
(b) [2 marks] What is a mapping reduction A ≤m B from language A to language B? Give both a formal
definition, and a brief intuitive explanation in your own words.
(c) [2 marks] What is a computable function? Give both a formal definition, and a brief intuitive explanation
in your own words.
(d) [3 marks] Suppose A ≤m B for languages A and B. Please answer each of the following with a brief
explanation.
i. If B is decidable, is A decidable?
ii. If A is undecidable, is B undecidable?
iii. If B is undecidable, is A undecidable?
3. [40 marks] Prove using reductions that the following languages are undecidable.
(a) [8 marks] L = {hMi | M is a TM and L(M) = Σ∗}.
(b) [8 marks] L = {hMi | M is a TM and {000, 111} ⊆ L(M)}.
(c) [8 marks] L = {hMi | M is a TM which accepts all strings of even parity}. (Recall the parity of a string
x ∈ {0, 1} is the number of 1’s in x.)
(d) [8 marks] L =
hMi | M is a TM that accepts w
R whenever it accepts w
. Recall here that w
R is the
string w written in reverse, i.e. 011R = 110.
(e) [8 marks] Consider the problem of determining whether a TM M on an input w ever attempts to move its
head left when its head is on the left-most tape cell. Formulate this problem as a language and show that it
is undecidable.
1