Models of Computation - Mathematics 352 - Fall 2009

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. We proved in an earlier homework (p. 45, Problem 1) that the inverse of every total, injective, unary, computable function is computable. Show, using Church's Thesis, that the hypothesis of "total" is not necessary; i.e., prove that the inverse of every injective, unary, computable function is computable. Where do you use the hypothesis of "injective" in your proof?
   Hint: Given a URM-program for f, how would you compute f ^-1 for a given input, using pencil and paper? Hint #2: do multitasking (parallel computing)!
3. 1. Show that if f : S --> S' is a bijection and S is denumerable, then S' is denumerable.
   2. Given that every infinite subset of N is denumerable, show that every infinite subset of a denumerable set is denumerable.