%I A060843
%S A060843 1,6,21,107
%N A060843 Busy Beaver problem: maximal number of steps that an n-state Turing machine 
               can make on an initially blank tape before eventually halting.
%C A060843 "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.
%C A060843 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).
%C A060843 Given that 5-state machines can compute Collatz-like congruential functions 
               (see references), it may be very hard to find the next term.
%C A060843 The sequence grows faster than any computable function of n and so is 
               non-computable.
%D A060843 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]
%D A060843 Brady, A. H. The determination of Rado's noncomputable function Sigma(k) 
               for four-state Turing machines, Math. Comp. 40 #62 (1983) 647-665.
%D A060843 Machlin, R. (nee Kopp) and Stout, Q, The Complex Behavior of Simple Machines, 
               Physica D 42 (1990) 85-98
%D A060843 Michel, Pascal, Busy beaver competition and Collatz-like problems, Arch. 
               Math. Logic (1993) 32:351-367.
%D A060843 R. M. Robinson, Minsky's small universal Turing machine, Int'l Jnl. Math, 
               2 #5 (1991) 551-562.
%D A060843 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.
%D A060843 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.
%D A060843 Claude E. Shannon, A universal Turing machine with two internal states, 
               Automata Studies, Ann. of Math. Stud. 34 (1956) 157-165.
%H A060843 Scott Aaronson, <a href="http://www.cs.berkeley.edu/~aaronson/bignumbers.html">
               Who Can Name the Bigger Number?</a>
%H A060843 Bill Dubuque, <a href="http://groups.google.com/groups?selm=WGD.96Feb13081831%40berne.ai.mit.edu">
               Re: Halting is weak</a>
%H A060843 A. Gravell and U. Ultes-Nitsche, <a href="http://www.ecs.soton.ac.uk/
               ~uun/CM219/HTML/sld169.htm">BB(n) Grows Faster Than Any Computable 
               Function</a>
%H A060843 H. Marxen, <a href="http://www.drb.insel.de/~heiner/BB/">Busy Beaver 
               Problem</a>
%H A060843 M. Somos, <a href="http://grail.cba.csuohio.edu/~somos/bb.html">Busy 
               Beaver Turing Machine</a>
%H A060843 M. Somos, <a href="http://grail.cba.csuohio.edu/~somos/busy.html">Busy 
               Beaver</a>
%H A060843 Q. F. Stout, <a href="http://www.eecs.umich.edu/~qstout/abs/busyb.html">
               The Complex Behavior of Simple Machines</a>
%H A060843 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               BusyBeaver.html">Link to a section of The World of Mathematics.</
               a>
%H A060843 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               BusyBeaver.html">Busy Beaver</a>
%H A060843 <a href="Sindx_Br.html#beaver">Index entries for sequences related to 
               Busy Beaver problem</a>
%Y A060843 Cf. A028444.
%Y A060843 Sequence in context: A012662 A012418 A083558 this_sequence A026650 A009253 
               A012840
%Y A060843 Adjacent sequences: A060840 A060841 A060842 this_sequence A060844 A060845 
               A060846
%K A060843 hard,nice,nonn,bref
%O A060843 1,2
%A A060843 Jud McCranie (j.mccranie(AT)comcast.net) and N. J. A. Sloane (njas(AT)research.att.com), 
               May 02 2001
%E A060843 The next two terms are at least 47176870 and 3*10^1730.
%E A060843 Additional references from Bill Dubuque (wgd(AT)martigny.ai.mit.edu)