

A060843


Busy Beaver problem: a(n) = maximal number of steps that an nstate Turing machine can make on an initially blank tape before eventually halting.


7




OFFSET

1,2


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 Juergen 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 twoway 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 5state 2symbol halting Turing machines can compute Collatzlike 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 0506 2011: (Start)
A more precise definition might be as follows:
Busy Beaver Problem: a(n) is the maximal number of steps that an nstate, 2symbol, d+ in {LEFT, RIGHT}, 5tuple (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 nonblank 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 2symbol BBclass 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


REFERENCES

A. H. Brady, The busy beaver game and the meaning of life, in Herken, R. (Ed) The Universal Turing Machine: A HalfCentury Survey, pp. 259277, Oxford Univ Press 1988. Reprinted by SpringerVerlag, 1995 (see pages 237254).
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 AllUnion 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. 7690.
Jeffrey Shallit, A second course in formal languages and automata theory. Cambridge University Press, 2008. See Fig. 6.2, p. 185.


LINKS

Table of n, a(n) for n=1..4.
Scott Aaronson, Who Can Name the Bigger Number?
Scott Aaronson, The busy beaver frontier, ACM SIGACT News 51.3 (2020): 3254.
A. H. Brady, The determination of Rado's noncomputable function Sigma(k) for fourstate Turing machines, Math. Comp. 40 #62 (1983) 647665.
Bill Dubuque, Re: Halting is weak
Daniel Forgues, Busy Beaver numbers
A. Gravell and U. UltesNitsche, BB(n) Grows Faster Than Any Computable Function [dead link]
Shawn Ligocki, BB(6,2) > 10^^15, Jun 21 2022.
Shen Lin and T. Rado, Computer Studies of Turing Machine Problems, J. ACM 12 (1965), 196212.
Rona Machlin (nee Kopp) and Quentin F. Stout, The Complex Behavior of Simple Machines, Physica D 42 (1990) 8598.
H. Marxen, Busy Beaver Problem
Pascal Michel, Busy beaver competition and Collatzlike problems, Arch. Math. Logic (1993) 32:351367.
Pascal Michel, Historical survey of Busy Beavers, 2011.
Pascal Michel, Behavior of busy beavers, 2010.
Pascal Michel, The Busy Beaver Competitions, 2010.
Pascal Michel, The Busy Beaver Competition: a historical survey, arXiv, 2010.
John Pavlus, How the Slowest Computer Programs Illuminate Math's Fundamental Limits, Quanta Magazine, Dec 10 2020.
T. Rado, On NonComputable Functions, Bell System Technical J. 41 (1962), 877884.
Raphael M. Robinson, Minsky's small universal Turing machine, Int'l Jnl. Math, 2 #5 (1991) 551562.
Claude E. Shannon, A universal Turing machine with two internal states, Automata Studies, Ann. of Math. Stud. 34 (1956) 157165.
Michael Somos, Busy Beaver Turing Machine
Michael Somos, Busy Beaver
Q. F. Stout, The Complex Behavior of Simple Machines
The Busy Beaver Challenge
Eric Weisstein's World of Mathematics, Busy Beaver
Index entries for sequences related to Busy Beaver problem


CROSSREFS

Cf. A028444.
Sequence in context: A203295 A318566 A083558 * A026650 A347948 A298837
Adjacent sequences: A060840 A060841 A060842 * A060844 A060845 A060846


KEYWORD

hard,nice,nonn,more


AUTHOR

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


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


STATUS

approved



