Models of Computation - Mathematics 450 - Fall 2006

For HW #16

1. The hint in problem 1(b) page 106 refers to the predicate "phi_x is total''; but there doesn't seem to be any theorem in this section of the book that proves this predicate is undecidable. (It is implied as a corollary of Rice's Theorem (1.7), but not stated explicitly as a theorem.)  So let's prove it ourselves, directly:
   Assume "phi_x is total'' is decidable, and derive a contradiction by constructing a unary computable function g that is different from phi_x for every x. Hint: let g(x) = phi_x(x)+1 if phi_x is total, 0 otherwise.