Massachusetts Institute of Technology Handout 33 6.042J/18.062J: Mathematics for Computer Science April 7, 2000 Professors David Karger and Nancy Lynch

Mini-Quiz 9

1. Write your name:

2. (Rosen, Section 1.7, Problem 35) Show that if A is an uncountable set and A ⊆ B, then B is uncountable.

Tutorial 9 Problems

Problem 1

(a) How many ways can 2n people be divided into n pairs?

(b) How many ways can you choose n out of 2n objects, given that n of the 2n objects are identical?

Problem 2 Calculate the number of ways to place 11 indistinguishable balls in four distinguishable boxes so that each box contains at least one, but no more than four, balls.

Problem 3 In this problem we will prove the remarkable fact that there exist mathematical functions that computers, no matter how powerful, simply cannot compute. We will do this through countability arguments.

(a) Show that the set of finite length binary strings is countable.

(b) From your answer to the previous part, what can you conclude about the countability of the set of all computer programs?

(c) Show that the set of infinite length binary strings is uncountable.

(d) A function is a decision function if it maps finite length bit strings into the range {0, 1}. Let F be the set consisting of all possible decision functions. Show that set F is uncountable.

(e) A function is computable if there is a computer program that computes it. From your answers to the previous parts, prove that there is a decision function that is not computable.