TL203F Algorithms, Logic and Complexity

Homework 3

We have now covered the first two chapters of the textbook. In the coming week we will see Turing machines, how they are used, and define Turing computability. This material is in Chapter 3.


  1. Let S be the set of all finite subsets of P (i.e. positive integers). This set is infinite but enumerable. What happens when we apply the diagonal argument to S? Show that we can not use the diagonal argument to show that S is not enumerable.
    [This is an issue that we talked about in lecture on monday Jan. 13th]

  2. [Exam 2013] Let A and B be two infinite sets. A is enumerable, but B is not enumerable.
    1. Show that AB is not enumerable.
    2. Show that AB is enumerable.
    3. What happens in a) and b) above if A is also not enumerable. Justify your answers.

  3. Problem 2.3 on page 20 in the textbook. Note that you have to use all of the real numbers.

  4. Let BS be the set of all infinite binary strings, i.e. each string in BS only has the symbols 0 or 1, and is of infinite length. Show that BS is not enumerable.

  5. Let F be the set of total functions from P to P, where P is the set of positive integer. Show that F is not enumerable.

Hand this homework in before 12:00 on friday January 24th.

hh (hja), January 17th, 2014.