Models of Computation - Mathematics 450 - Spring 2005

For HW #17

1. We already did this problem in class. Now try to redo it and write a careful solution in your own words, without looking at your notes.
   Explain what is wrong with the following alleged proof for showing that "phi_x = 0" is undecidable.
   Wrong 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. Then, by Church's Thesis, f is computable. And, clearly, 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.
3. The Busy Beaver Problem (revisited).
   Let B(n) = the largest possible output for any n-instruction URM program starting with zeros in all registers. Prove that B is not computable, by combining the following steps.
   1. Prove that for all n, B(n+1) > B(n).
   2. Show that for every n >= 16, there is an n-instruction URM program whose productivity (i.e., its output, starting with zeros for input) is greater than 2n. Hint: Write n-8 S(1)'s, then write eight more instructions to quadruple register 1.
   3. Suppose, towards contradiction, that there is a program P that computes B. Let k be twice the number of instructions in P, or 32 (= 2 x 16), whichever is larger. Show that you can prepend P by a program from part (b) to get a program with k or fewer instructions whose productivity is greater than B(k).