Main Page

From BusyBeaverWiki
Jump to navigation Jump to search

The Busy Beaver function BB (called S originally) was introduced by Tibor Radó in 1962 [1] for 2-symbol Turing machines and later generalised[2] to m-symbol Turing machines:

BB(n,m) = Maximum number of steps taken by a halting n-state, m-symbol Turing machine starting from a blank (all 0) tape

The 2-symbol case BB(n,2) is abbreviated as BB(n). The busy beaver function is not computable, and few of its values are known:

Small busy beaver values [3] [4]
2-state 3-state 4-state 5-state 6-state 7-state
2-symbol BB(2) = 6 BB(3) = 21 BB(4) = 107 BB(5) = 47,176,870 BB(6) > BB(7)
3-symbol BB(2,3) = 38 BB(3,3) > BB(4,3) >
4-symbol BB(2,4) = 3,932,964 BB(3,4)
5-symbol BB(2,5) > 6.5 ×

In the above table, cells are highlighted in orange when there are known Cryptids (mathematically-hard machines) in that class, and cells are highlighted in light orange when the existence of a Cryptid is given by using a known one with less states or symbols.

bbchallenge.org

bbchallenge.org [4] is a massively collaborative research project whose general goal is to obtain more knowledge on the Busy Beaver function. In practice, it mainly consists in collaboratively building Deciders, programs that automatically prove that some Turing machines do not halt. Other efforts also include:

Notably, as part of bbchallenge.org, in June 2024 the 5th busy beaver value BB(5) was proven in Coq to be equal to the lower bound found in 1989[5]: 47,176,870.

Contribute to this wiki

This wiki is collaborative, feel free to contribute by editing existing pages or creating new ones:

Notes

  1. Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x
  2. Brady, Allen H, and the Meaning of Life, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey (Oxford, 1990; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 8 June 2024.
  3. https://bbchallenge.org/~pascal.michel/ha.html
  4. 4.0 4.1 https://bbchallenge.org/
  5. H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html