In order to pass this assignment you have to get at least two points.
(1p) State and give a brief explanation of the Church-Turing thesis.
(1p) Give an example of a function on the natural numbers (from ℕ to ℕ) that is:
Injective but not surjective.
Bijective.
(1p) Is ℕ × Bool countable? Provide a proof. (Bool is a set with two elements, true and false.)
(1p) [BN] Is ℕ → Bool countable? Provide a proof.
(Exercises marked with [BN] are based on exercises from a previous version of this course, given by Bengt Nordström.)