Models of Computation - Mathematics 450 - Fall 2006

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 each of the following true or false? Explain why. (1) Every enumerable set is denumerable. (2) Every enumerable set is effectively denumerable. (3) Every denumerable set is enumerable.  (Be careful; don't guess the answer; read the definitions carefully!)
2. (Optional ) 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. (Optional) Can you guess why in Theorem 1.4 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 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 are some "real" math problems:
   
   
4. (a) Define g : N⁺ x N⁺ --> N⁺ as follows (where N⁺ is the set of positive natural numbers): g(1,1) = 1, g(1,2) = 2, g(2,1) = 3, g(1,3) = 4, g(2,2)= 5, g(3,1) = 6, g(1,4) = 7, g(2,3) = 8, g(3,2) = 9, g(4,1) = 10, etc. (pictorially, we're traveling along lines of slope -1 on the xy-plane).  Find a "closed form" formula for g(x,y) in terms of x and y. (Optional: can you prove rigorously that g is a bijection?)
   (b) Assuming that g is a bijection, prove, without using Church's Thesis, that g^-1 is computable. You may use the "standard" computable functions of Chapter 2 (such as x+y, xy, |x-y|, sg(x), etc.) as well as substitution, recursion, and minimalization.
   (c) In class we listed (i.e., enumerated) the elements of Q⁺ (the positive rationals) according to the following pattern: 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, etc. Define f : N --> Q⁺ as follows: f(0) = 1/1, f(1) = 1/2, f(2) = 2/1, f(3) = 1/3, f(4) = 2/2, f(5) = 3/1, f(6) = 1/4, f(7) = 2/3, f(8) = 3/2, f(9) = 4/1, etc.  Prove, without using Church's Thesis, that f is computable. Hint: use part (b) and projection functions.
   (d)  Is Q⁺ effectively denumerable or just denumerable? Justify your answer.
   (Hopefully, this will further convince you of Church's Thesis -- more specifically, that when humans do something algorithmically, a URM can do it too, even when the human algorithm involves following a (pictorial) pattern!)
5.  
   1. Give a computable bijection phi: N x N x N --> N.
   2. Suppose f : N x N x N --> N is a total computable function. Define g(w) = 1 if there exist x, y, z such that f(x,y,z) = w; and g(w) is undefined otherwise. Use Church's Thesis to prove g is computable. (Hint: use part a. We did a problem similar to this in class for f : N x N --> N.)
      
6. State whether or not (you think) each of the following functions is computable. We have not yet proved any functions to be non-computable. We will do so in the next chapter. For this problem, if you believe a function is not computable, explain why you believe so; but no proof is necessary. If you think a function is computable, give a proof by Church's Thesis.
   
   1. f(x) = 1 if x is in Dom(g), 0 otherwise, where g(x) is a computable function.
   2. f(x) = 1 if p_x (the xth prime) is in Dom(g), undefined otherwise, where g(x) is a computable function.
   3. f(x) = 1 if p_x (the xth prime) is not in Dom(g), undefined otherwise, where g(x) is a computable function.
   4. f(x) = 1 if Dom(g) is nonempty, undefined otherwise, where g(x) is a computable function.