1,2

"In 1965 [Tibor] Rado, together with Shen Lin, proved that BB(3) is 21. ... Next, in 1983, Allan Brady proved that BB(4) is 107. ... Then, in 1989, Heiner Marxen and Juergen Buntrock discovered that BB(5) is at least 47,176,870. ... As for BB(6), Marxen and Buntrock set another record in 1997 by proving that it is at least 8,690,333,381,690,951." Aaronson.

The function Sigma(n) (A028444) denotes the maximal number of tape marks which a Turing Machine with n internal states and a two-way infinite tape can write on an initially empty tape and then halt. The function S(n) (the present sequence) denotes the maximal number of steps (shifts) which such a machine can make (it needs not produce many tape marks).

Given that 5-state 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 non-computable.

Brady, A. H., 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). [Reference updated by Daniele Giorgio Degiorgi, Nov 22 2008]

Brady, A. H. The determination of Rado's noncomputable function Sigma(k) for four-state Turing machines, Math. Comp. 40 #62 (1983) 647-665.

Machlin, R. (nee Kopp) and Stout, Q, The Complex Behavior of Simple Machines, Physica D 42 (1990) 85-98

Michel, Pascal, Busy beaver competition and Collatz-like problems, Arch. Math. Logic (1993) 32:351-367.

R. M. Robinson, Minsky's small universal Turing machine, Int'l Jnl. Math, 2 #5 (1991) 551-562.

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.

Claude E. Shannon, A universal Turing machine with two internal states, Automata Studies, Ann. of Math. Stud. 34 (1956) 157-165.

Scott Aaronson, Who Can Name the Bigger Number?

Bill Dubuque, Re: Halting is weak

A. Gravell and U. Ultes-Nitsche, BB(n) Grows Faster Than Any Computable Function

H. Marxen, Busy Beaver Problem

M. Somos, Busy Beaver Turing Machine

M. Somos, Busy Beaver

Q. F. Stout, The Complex Behavior of Simple Machines

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Busy Beaver

Index entries for sequences related to Busy Beaver problem

Cf. A028444.

Sequence in context: A012662 A012418 A083558 this_sequence A026650 A009253 A012840

Adjacent sequences: A060840 A060841 A060842 this_sequence A060844 A060845 A060846

hard,nice,nonn,bref

Jud McCranie (j.mccranie(AT)comcast.net) and N. J. A. Sloane (njas(AT)research.att.com), May 02 2001

The next two terms are at least 47176870 and 3*10^1730.

Additional references from Bill Dubuque (wgd(AT)martigny.ai.mit.edu)