Computers and Reality - Cognitive Science 110 - Spring 2007

Problems 1 and 3 are optional. If you do them, turn them in to me, not to the grader.

1. Extra Credit: Prove that the following function is not computable; do this by showing that if it were computable, then the Halting Problem would be decidable (which we know isn't the case).

   f(x,y) = {

   1                 if  Px(y) does not stop undefined    otherwise

2. Busy Beaver: "number-of-steps version".
   1. Let's define the step-productivity of a URM program as the number of instructions that are performed before the program stops, starting with input zero. Write a program whose step-productivity is larger than its number of lines (instructions). What is the smallest such program (i.e., with the fewest number of lines) that you can find?
   2. Let BBS(n) = the largest possible step-productivity of all n-line URM programs. Prove that the function BBS is not computable by showing that if it were computable, then the Halting Problem would be decidable.
      Hint: Given any x and y, to determine whether P_x(y) stops, add S(1)  y times to the beginning of P_x; call this new program P'. Then use BBS to determine whether P'(0) stops.
3. Extra Credit: Prove that the Halting Problem is not decidable by showing that if it were decidable, then the (original) Busy Beaver function beta(n) would be computable. Explain and justify the following: Our proof that beta(n) is not computable implies (by some of the problems in this HW set) that BBS(n) is not computable.