cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A060843 Busy Beaver problem: a(n) is the maximal number of steps that an n-state Turing machine can make on an initially blank tape before eventually halting.

Original entry on oeis.org

1, 6, 21, 107, 47176870
Offset: 1

Views

Author

Jud McCranie and N. J. A. Sloane, May 02 2001

Keywords

Comments

"In 1965 Tibor Rado, together with Shen Lin, proved that a(3) is 21. (...) Next, in 1983, Allan Brady proved that a(4) is 107. (...) Then in 1989 Heiner Marxen and Jürgen Buntrock discovered that a(5) is at least 47176870. (...) As for a(6), Marxen and Buntrock set another record in 1997 by proving that it is at least 8690333381690951." [Based on Aaronson's web page.]
The function Sigma(n) = Sigma(n, 2) (A028444) denotes the maximal number of tape marks (1's) that a Turing Machine with n internal states (plus the Halt state), 2 symbols, and a two-way infinite tape can write on an initially blank tape (all 0's) and then halt. The function a(n) (the present sequence) denotes the maximal number of steps S(n) = S(n, 2) (thus shifts, since direction NONE is excluded) that such a machine can make (not necessarily the same Turing machine producing a maximum number of 1s and need not even produce many tape marks).
Given that 5-state 2-symbol halting Turing machines can compute Collatz-like congruential functions (see references), it may be very hard to find the next term.
The sequence grows faster than any computable function of n and so is noncomputable.
From Daniel Forgues, Jun 05-06 2011: (Start)
A more precise definition might be as follows:
Busy Beaver Problem: a(n) is the maximal number of steps that an n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) Turing machine can make on an initially blank tape and then halt.
Further comments:
H in H_(n, k) is a halting* Turing machine with n states and k symbols;
* (on a blank tape (all 0's) as input)
States q, q+ in set Q_n of n distinct states (plus the Halt state);
Symbols s, s+ in set S_k of k distinct symbols (0 as the blank symbol);
Shift direction d+ in {LEFT, RIGHT} (NONE is excluded here);
sigma(H) is the number of non-blank symbols left on the tape by H;
s(H) is the number of steps (or shifts in our case) taken by H;
Sigma(n, k) = max {sigma(H) : H is a halting Turing machine with n states and k symbols}
S(n, k) = max {s(H) : H is a halting Turing machine with n states and k symbols}
a(n) is S(n) = S(n, 2) since a 2-symbol BB-class Turing machine is assumed.
For all n, S(n, k) >= Sigma(n, k), k >= 2. (End)
a(6) > 10^^15, a tower of 10's of height 15 [Pavel Kropitz] - see Shawn Ligocki's blog. - N. J. A. Sloane, Jun 22 2022
It is conjectured that a(5) = 47176870 (Conjecture 10 of the Scott Aaronson link "The busy beaver frontier"). - Jianing Song, Feb 21 2024
On July 02, 2024 cosmo (Tristan Stérin) on behalf of the Busy Beaver Challenge group announced: "We have proved 'BB(5) = 47,176,870'". - Peter Luschny, Jul 02 2024
The next term is much too large to include in the OEIS or even to conceive. The BBchallenge has found this month (cf. Scott Aaronson link from June 2025) that a(6) > 2^^^5 >> 10^^(10^7) where the repeated ^ stands for Knuth's arrow notation; 10^^(10^7) (tetration) means the power tower 10^(10^(...)) with 10^7 nested "^10" in the exponent, and ^^^ means pentation which is repeated tetration (cf. Wikipedia). - M. F. Hasler, Jun 30 2025

References

  • A. H. Brady, The busy beaver game and the meaning of life, in Herken, R. (Ed) The Universal Turing Machine: A Half-Century Survey, pp. 259-277, Oxford Univ Press 1988. Reprinted by Springer-Verlag, 1995 (see pages 237-254).
  • J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010; see p. 33.
  • Yu. V. Rogozhin, Seven universal Turing machines (Russian), abstract, Fifth All-Union Conference on Math. Logic, Akad. Nauk. SSSR Sibirsk. Otdel., Inst. Mat., Novosibirsk, 1979, p. 127.
  • Yu. V. Rogozhin, Seven universal Turing machines (Russian), Systems and Theoretical Programming, Mat. Issled. no. 69, Akademiya Nauk Moldavskoi SSSR, Kishinev, 1982, pp. 76-90.
  • Jeffrey Shallit, A second course in formal languages and automata theory. Cambridge University Press, 2008. See Fig. 6.2, p. 185.

Links

Crossrefs

Cf. A028444, A362199.

Extensions

Additional references from Bill Dubuque (wgd(AT)martigny.ai.mit.edu)
Edited by N. J. A. Sloane, Aug 30 2011
Additional links from Robert C. Lyons, Jun 22 2022
a(5) added by Charles R Greathouse IV, Jul 02 2024

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.