Definition: (1) A Turing machine with a small number of states that halts when started with a blank tape, but 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 impractical to determine for even a small number of states and symbols. This problem is related to the halting problem since one must determine if a machine is looping or eventually halts.
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 2 November 2007.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "busy beaver", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 2 November 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/busyBeaver.html