Busy Beaver

A busy beaver is an $n$-state, 2-symbol, 5-tuple Turing Machine which writes the maximum possible number ${\it BB}(n)$ of 1s on an initially blank tape before halting. For $n = 0$, 1, 2, ..., ${\it BB}(n)$ is given by 0, 1, 4, 6, 13, $\geq 4098$, $\geq 136612$, .... 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.