(classic problem)
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.
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 Black.
Entry modified 26 July 2021.
HTML page formatted Mon Jul 26 11:58:06 2021.
Cite this as:
Paul E. Black, "busy beaver", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 26 July 2021. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/busyBeaver.html