## 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