Models of Computation - Mathematics 450 - Fall 2006

For HW #15

1. Let {g₀, g₁, g₂, g₃, ...} be an enumeration of all primitive recursive functions. Let f(x) = g_x(x) +1. Explain why f is total, computable, and not primitive recursive.
2. A paradox: Let f(x) = phi_x(x) +1 if phi_x(x) is defined, undefined otherwise (recall that phi_x is the unary function computed by program P_x). Then it seems easy to show that: (1) f is computable, and (2) f is different from phi_x for every x. But this gives a contradiction, because if f is computable, then it must equal phi_x for some x. Resolve this paradox.
3. The Busy Beaver Problem (Part 2).
   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: For n = 16, write n-8  S(1)'s, then write eight more instructions to quadruple register 1; then take care of all n > 16.
   3. Suppose, towards contradiction, that there is a program P that computes the function B.  Let k be the number of instructions in P. Show that you can prepend P by a program from part (b) to get a program with n <= 2max(k, 16) instructions whose productivity is greater than B(n).