Models of Computation - Mathematics 352 - Fall 2009

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 > m, B(n) > B(m).
   2. Show that for every n >= 20, there is an n-instruction URM program whose productivity (i.e., its output, starting with zeros for input) is strictly greater than 2n and when it stops, registers R2, R3, ... all contain 0. Hint: For n = 20, write 10  S(1)'s, then write at most ten more instructions to quadruple register 1 and put zeros in the other registers. Then take care of all n > 20.
   3. Suppose, toward contradiction, that there is a program P that computes the function B.  Show that you can "prefix" ("opposite" of "append") P by a program from part (b) to get a program with m instructions whose productivity is strictly greater than B(m).