A busy beaver is an -state, 2-symbol, 5-tuple Turing Machine which writes the maximum possible number of 1s on an initially blank tape before halting. For , 1, 2, ..., is given by 0, 1, 4, 6, 13, , , .... The busy beaver sequence is also known as Rado's Sigma Function.
See also Halting Problem, Turing Machine
References
Chaitin, G. J. ``Computing the Busy Beaver Function.'' §4.4 in
Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath).
New York: Springer-Verlag, pp. 108-112, 1987.
Dewdney, A. K. ``A Computer Trap for the Busy Beaver, the Hardest-Working Turing Machine.'' Sci. Amer. 251, 19-23, Aug. 1984.
Marxen, H. and Buntrock, J. ``Attacking the Busy Beaver 5.'' Bull. EATCS 40, 247-251, Feb. 1990.
Sloane, N. J. A. Sequence
A028444
in ``The On-Line Version of the Encyclopedia of Integer Sequences.''
http://www.research.att.com/~njas/sequences/eisonline.html.