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 Black.
Entry modified 12 February 2019.
HTML page formatted Wed Mar 13 12:42:45 2019.
Cite this as:
Paul E. Black, "busy beaver", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 12 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/busyBeaver.html