Models of Computation - Mathematics 450 - Spring 2005

For HW #18

1. Combine the following steps to give a proof of Rice's Theorem (p. 105) by Church's Thesis. (The proof given below is essentially the same as the book's proof. The main difference is that it resorts to Church's Thesis instead of the s-m-n Theorem.)
   Let B be a non-empty proper subset of the set of all unary computable functions. If "j_x e B " were decidable, then we would be able to solve the Halting Problem: given m, n in N, we would decide whether or not P_m(n) halts, by the following algorithm.
   1. Let u(x) = undefined for all x. Explain in detail how we can use the algorithm for "j_x e B " to decide whether or not the function u is in B.
   2. Explain in detail how we can use the algorithm for "j_x e B " to find two computable functions f and g such that f is in B and g is not in B.
   3. Suppose u is in B. (We'll deal with the case when u is not in B later.) Let h(x) = g(x) if P_m(n) halts, undefined otherwise. Prove by Church's Thesis that h is computable.
   4. Explain carefully and in detail how we can use the function h and the algorithm for "j_x e B " to decide whether or not P_m(n) halts.
   5. Now suppose u is not in B. Explain how you would define h differently and then use it to decide whether or not P_m(n) halts.