Models of Computation - Mathematics 450 - Spring 2005

For HW #13

1. Let f(x) = x (the identity function), and g(x) = x+2. According to the way we numbered URM programs in class (rather than the book's numbering), does f have an index less than 20? How about g? Why? (See page 77 for the definition of index.)
2. Use a diagonal argument to prove the set of total, unary functions is not denumerable.
3. Prove that every infinite subset of a denumerable set is denumerable.
4. Let S be the set of all total, computable, unary functions.
   1. Prove S is denumerable.
   2. Use a diagonal argument to prove S is not effectively denumerable.
   3. Let t(x) = 1 if phi_x (the function computed by program number x) is total, 0 otherwise. Prove by Church's Thesis that t is not computable. Hint: Use (b).