(classic problem)
Definition: (1) A Turing machine with a small number of states which halts when started with a blank tape, but which writes a huge number of non-blanks or takes a huge number of steps. (2) The problem of finding the maximum number of non-blanks written or steps taken for any Turing machines with a given number of states and symbols.
Note: The problem is well-defined but rapidly becomes uncomputable for even a small number of states and symbols.
Author: PEB
History, explanation, and links about the Busy Beaver Turing Machine. Heiner Marxen's currently known busy beaver results page.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified Fri Dec 17 11:48:59 2004.
HTML page formatted Wed Oct 26 09:47:18 2005.
Cite this as:
Paul E. Black, "busy beaver", from
Dictionary of Algorithms and Data
Structures, Paul E. Black, ed.,
NIST.
http://www.nist.gov/dads/HTML/busyBeaver.html
