The function BB is defined in terms of Turing machines with a purely binary tape alphabet (no blanks) in quintuple format (rather than quadruple format used before). For each n define the set An = {i : Ti has n states and φi(0) < ∞}. That is, Ti with i in An halts when it is started with p = . We define BB(n) as the maximal number of 1s in the output of any Turing machine in An when it is started on input . It is easy to see that BB(1) = 1, but more difficult to see that BB(2) = 4.
The BB function is known as the busy beaver function. It is due to T.
Rado [Bell System Tech. J. (1962), 877–884]. This was one of the first ‘well-defined’ incomputable total functions. The definition is natural and uses no overt diagonalization.

(a) [12] Notice that the BB function is well defined, since you can show that d(An) ≤ (6n)2n.

(b) [15] Show that the BB function is incomputable. (Hint: It grows faster than any computable function.)

(c) [35] Show that BB(3) = 6.

(d) [40] Show that BB(4) = 13.

(e) [30] Can you give a lower bound on BB such as the Ackermann generalized exponential function?

(f) [O45] Is BB(5) > 4,098?
Comments. See [A.K. Dewdney, Scientific American, 251 (August 1984), 19–23; Ibid, 252 (March 1985), 23; A.H. Brady, pp. 259–278 in: The Universal Turing Machine: A Half-Century Survey, R. Herken, ed., Oxford Univ. Press, 1988; H. Marxen and J. Buntrock, EATCS Bull., 40(1990), 247–251]. For the quadruple format see [A. Oberschelp, K. SchmidtGoettsch, G. Todt, Castor Quadruplorum, Archive for Math. Logic, 27(1988), 35–44].