Computers and Reality - Cognitive Science 110 - Spring 2007

1. Recall that we denote the busy beaver function by:  beta(n) = the largest possible productivity for all n-line URM-programs. Prove that if n > m, then beta(n) > beta(m).
2. Prove that for every n >= 18, there is an n-line URM-program that, given input 0, eventually stops with R₁ >= 2n and 0 in all the remaining registers.
3. (Do not turn in this problem -- if you want to write it up and have it graded, bring it to me during office hours.) Prove, without looking at your notes, that beta is not computable. (You may study your notes as much as you like; but once you start writing your proof, you may not go back to look again. The goal is to test yourself to see if you will be able to do this on the exam. In your proof you may refer to Problems 1 and 2 above without having to redo them.)