Busy Beaver

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.

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 A028444in ``The On-Line Version of the Encyclopedia of Integer Sequences.''http://www.research.att.com/~njas/sequences/eisonline.html.

• Ludolph's Constant
• Ludwig's Inversion Formula
• Lukács Theorem
• Lune (Plane)
• Lune (Solid)
• Lune (Surface)
• Lunule
• Lusin's Theorem
• LUX Method
• Lyapunov Characteristic Exponent
• Lyapunov Characteristic Number
• Lyapunov Condition
• Lyapunov Dimension
• Lyapunov Function
• Lyapunov's First Theorem
• Lyapunov's Second Theorem
• Lyndon Word
• Lyons Group
• Léon Anne's Theorem
• Lévy Constant
• Lévy Distribution
• Lévy Flight
• Lévy Fractal
• Lévy Function
• Lévy Tapestry