Let g(x,y) be a total computable function. Define f(z) = 1 if z is in the range of g, undefined otherwise.
Prove by Church's Thesis that f is computable.
Give a formal proof, by using the methods of Chapter 2, that f is computable. For your proof, do you need the hypothesis that g is total? (Moral: sometimes not using Church’s Thesis gives a shorter proof!)
Now suppose g is computable but not total; is f still computable? If so, give a proof (formal proof, or by Church's Thesis). If not, explain your reasoning.
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 #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.
The Busy Beaver Problem. This problem was invented by Tibor Rado: Bell System Technical Journal, 1962.
Let B(n) = the largest possible output for any n-instruction URM program starting with zeros in all registers.
Prove that B(n) is greater than or equal to n, for all n.
(Optional) Find the smallest n you can such that B(n) > n.
Let's define B(0) = 0 (because a program with no instructions gives output 0). Then, do you think B is a total or non-total function? Give a convincing and detailed argument to support your answer. (It's OK if your argument isn't rigorous.)
We show below that the function B is not computable.
Prove that for all n > m, B(n) > B(m).
Define the productivity of a URM program to be the output it produces starting with zeros for input (if the program doesn't stop, it's productivity is undefined). Show that for every n >= 20, there is an n-instruction URM program Q_n whose productivity 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.
Show the function B is not computable: Suppose, toward contradiction, that there is a program PB that computes B. Show that you can "prepend" (opposite of append) PB by some Q_n to get a program "Q_n + PB" whose productivity is strictly greater than B(m), where m is the number of instructions in "Q_n + PB".