Models of Computation - Mathematics 450 - Spring 2005

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. The Busy Beaver Problem (continued...)
   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. (Hints will be provided on the next HW set, if no one proves this before then.)