TÖL203F Algorithms, Logic and Complexity
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.
- 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]
- [Exam 2013] Let A and B be two infinite sets. A is enumerable, but B is not
- Show that A ∪ B is not enumerable.
- Show that A ∩ B is enumerable.
- What happens in a) and b) above if A is also not enumerable. Justify
- Problem 2.3 on page 20 in the textbook. Note that you have to use all of the real numbers.
- 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.
- 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) hi.is, January 17th, 2014.