Busy beaver

For the 1931 Silly Symphonies animated film, see The Busy Beavers. For the online children's educational program, see Busy Beavers.
This "space-time diagram"[1] shows the first 100,000 timesteps of the best 5-state busy beaver from top to bottom. Orange is "1", white is "0" (image compressed vertically).

In theoretical computer science, the busy beaver game aims at finding a terminating program of a given size that (depending on definition) either produces the most output possible, or runs for the longest number of steps.[2] Since an endlessly looping program producing infinite output or running for infinite time is easily conceived, such programs are excluded from the game.[2] Rather than traditional programming languages, the programs used in the game are n-state Turing machines,[2] one of the first mathematical models of computation.[3]

Turing machines consist of an infinite tape, and a finite set of states which serve as the program's "source code". Producing the most output is defined as writing the largest number of 1s on the tape, also referred to as achieving the highest score, and running for the longest time is defined as taking the longest number of steps to halt.[4] The n-state busy beaver game consists of finding the longest-running or highest-scoring Turing machine which has n states and eventually halts.[2] Such machines are assumed to start on a blank tape, and the tape is assumed to contain only zeros and ones (a binary Turing machine).[2] A player should conceive of a set of transitions between states aiming for the highest score or longest running time while making sure the machine will halt eventually.

An nth busy beaver, BB-n or simply "busy beaver" is a Turing machine that wins the n-state busy beaver game.[5] Depending on definition, it either attains the highest score, or runs for the longest time, among all other possible n-state competing Turing machines. The functions determining the highest score or longest running time of the n-state busy beavers by each definition are Σ(n) and S(n) respectively.[4]

Deciding the running time or score of the nth Busy Beaver is incomputable.[4] In fact, both the functions Σ(n) and S(n) eventually become larger than any computable function.[4] This has implications in computability theory, the halting problem, and complexity theory.[6] The concept was first introduced by Tibor Radó in his 1962 paper, "On Non-Computable Functions".[4] One of the most interesting aspects of the busy beaver game is that, if it were possible to compute the functions Σ(n) and S(n) for all n, then this would resolve all mathematical conjectures which can be encoded as "does this Turing machine halt or not".[5] For example, a 27-state Turing machine could check Goldbach's conjecture for each number and halt on a counterexample: if this machine had not halted after running for S(27) steps, then it must run forever, resolving the conjecture.[5] Many other problems, including the Riemann hypothesis (744 states) and the consistency of ZF set theory (745 states[7][8]), can be expressed in a similar form, where at most a countably infinite number of cases need to be checked.[5]

  1. ^ "The Busy Beaver Challenge: Story # space-time-diagrams". bbchallenge.org. Retrieved 2024-07-09.
  2. ^ a b c d e Weisstein, Eric W. "Busy Beaver". Wolfram MathWorld. Retrieved 21 November 2023.
  3. ^ Brubaker, Ben (2024-07-02). "Amateur Mathematicians Find Fifth 'Busy Beaver' Turing Machine". Quanta Magazine. Retrieved 2024-07-03.
  4. ^ a b c d e Radó, Tibor (May 1962). "On non-computable functions" (PDF). Bell System Technical Journal. 41 (3): 877–884. doi:10.1002/j.1538-7305.1962.tb00480.x.
  5. ^ a b c d Pavlus, John (10 December 2020). "How the Slowest Computer Programs Illuminate Math's Fundamental Limits". Quanta Magazine. Retrieved 2020-12-11.
  6. ^ Aaronson, Scott (2020-09-29). "The Busy Beaver Frontier". SIGACT News. 51 (3): 32–54. doi:10.1145/3427361.3427369. ISSN 0163-5700. PDF available from author.
  7. ^ Cite error: The named reference AaronsonJuly2023 was invoked but never defined (see the help page).
  8. ^ Riebel, Johannes (March 2023). The Undecidability of BB(748): Understanding Gödel’s Incompleteness Theorems (PDF) (Bachelor's thesis). University of Augsburg. Retrieved 24 September 2024.