CS4124 Theory of Computation

HW #1: 10 problems

Due Wednesday 1 September 1999 at 1200 hrs

Late policy: 10%/day up to 50% (weekends = 1 day)

If your paper is illegible, you will lose points

Most of these problems are from the book

1.3.2, 1.3.6 (p. 18f)

1.4.2 (p. 23)

1.5.2, 1.5.9 (p. 29)

Number this problem "1.5.x" (from John D. Baum, Elts of Point Set Topology, Prentice-Hall, 1964):

Criticize the following "proof" that the set of positive integers is uncountable. Write each positive integer in the usual way, but precede the first digit by an infinite string of zeros stretching off to the left, e. g., 17 is written …00017. Assume the set of positive integers is countable and set up the obvious one-to-one correspondence n « …000n. For example, 124 corresponds with …000124. Write the list of these down in the usual order, thus:

…0001

…0002

…0003

etc.

Now construct a new number as follows: reading down the diagonal entries in the above list, if the digit at the nth place in the nth number of the list is 5, let the entry in the new number at the nth place be 6, if the nth digit in the nth number of the list is different from 5, let the entry at the nth place of the new number be 5. The number thus constructed is different from the nth number in the list at the nth place, thus is different from all of them, and the one-to-one correspondence above constructed is not as claimed a one-to-one correspondence, whence the set of all positive integers is uncountable.

1.7.2 (p. 46)

1.8.2, 1.8.5, 1.8.6 (p. 51f)