Models of Computation - Mathematics 450 - Spring 2005

For HW #16

1. Explain what is wrong with the following alleged proof of "phi_x = 0".
   "Proof": Given x, there is no algorithm for deciding whether or not P_x stops for any given input (since the Halting Problem is undecidable). Therefore there is no algorithm for deciding if P_x(y) = 0 for all y.
2. A paradox: Let f(x) = phi_x(x) +1 if phi_x(x) is defined, undefined otherwise. It seems, then, that we can show (1) f is computable, and (2) f is different from phi_x for every x. So we get a contradiction, because if f is computable, then it must equal phi_x for some x. Resolve this paradox by finding a fallacy in this argument.

Hints for the Busy Beaver Problem will be provided on the next HW set, after the midterm.