Models of Computation - Mathematics 352 - Fall 2009

For HW #14

1. Let g(x,y) be a total computable function. Define f(z) = 1 if z is in the range of g, undefined otherwise.
   1. Prove by Church's Thesis that f is computable.
   2. Give a formal proof that f is computable (by using the methods of Chapter 2).
   3. If g were a non-total computable function, would f necessarily be computable? If so, give a proof by Church's Thesis. If not, explain your reasoning.
2. In parts b. and c. of this problem, we will see (for the first time) an example of a set that is denumerable but not effectively denumerable.
   1. Use a diagonal argument to prove the set of total, unary functions is not denumerable.
   2. Let S be the set of all total, computable, unary functions. Prove S is denumerable. Hint: In a previous HW we proved that every infinite subset of a denumerable set is denumerable.
   3. Use a diagonal argument to prove S is not effectively enumerable, and hence not effectively denumerable. You may assume that "S is effectively enumerable" means the following: S = {g₀, g₁, g₂, ...} and there is a computable bijection f: N --> N such that the URM-program whose number is f(n) computes g_n .
   4. Let t(x) = 1 if phi_x (the function computed by program number x) is total, 0 otherwise. Prove by Church's Thesis that t is not computable. Hint: show that if t(x) were computable, then S would be effectively enumerable, contradicting part c.
3. The Busy Beaver Problem (Part 1).
   Let B(n) = the largest possible output for any n-instruction URM program starting with zeros in all registers.
   1. Prove that B(n) is greater than or equal to n, for all n.
   2. Find the smallest n you can such that B(n) > n.
   3. Let's define B(0) = 0 (because a program with no instructions gives output 0). Then, do you think B is a total function? Give a convincing and detailed (but not necessarily rigorous) argument to support your answer.
   4. (Optional)  Let's have a contest: find the most productive 10-instruction URM program you can, i.e., a 10-instruction program with the largest output you can find, starting with zeros in all registers.