Models of Computation - Mathematics 450 - Spring 2005

For HW #12

In the following, N  denotes the set of all natural numbers.

1. Refer to Definitions 1.1(abc) for these problems.
   1. Is the set of natural numbers between 0 and 100 countable?
   2. Is the set of all natural numbers countable?
   3. What is the difference between "countable" and "denumerable"?
   4. What is the difference between "denumerable" and "effectively denumerable"?
   5. Let's say a set is enumerable if there exists an enumeration of it. Then, is "enumerable" equivalent to "denumerable" or to "effectively denumerable" or to neither? (Be careful; don't guess the answer; read the definitions carefully!)
2. Explain in your own words the Note on top of page 73 and the footnote at the bottom of the same page. In your explanation include answers to the following questions:  Why does the book use " the informal notion of effectively computable" ? Why shouldn't we instead require that the bijection f: X --> N be URM-computable?
3. Can you guess why the book uses the letter gamma for the bijection from the set of all programs to N? Hint: Read the paragraph after the proof of Theorem 1.4. If that hint didn't help, here's another one: read footnote 2 at the bottom of the same page.
   
   
   Okay, I guess all of the above were kind of unusual questions, at least for a math course! Nevertheless, I. and II. are important (and III. is amusing -- I hope). Now here's a "real" math problem:
   
   
4. In class, we listed (i.e., enumerated) the elements of N x N according to the following pattern: (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), (2,1), (1,2), (0,3), etc.; pictorially, we're going down lines of slope -1. Give a bijection f: N x N --> N that "corresponds" to this listing (give an "explicit formula" for the function f  -- you may use substitution, recursion, and minimalization, if convenient). Is N x N effectively denumerable or just denumerable?  Is f primitive recursive? Explain why.
   (Hopefully, this will further convince you that when humans do something algorithmically, a URM can do it too, even when the human algorithm involves following a pictorial pattern!)