Models of Computation - Mathematics 450 - Spring 2005

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. The Busy Beaver Problem.
   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.