Search: id:A028444
Results 1-1 of 1 results found.

%I A028444
%S A028444 0,1,4,6,13
%N A028444 Busy Beaver sequence, or Rado's sigma function: maximum number of 1's 
               that an n-state, 2-symbol, 5-tuple Turing machine can print on an 
               initially blank tape before halting.
%C A028444 The function Sigma(n) (A028444) denotes the maximal number of tape marks 
               which a Turing Machine (TM) with n internal states and a two-way 
               infinite tape can produce onto an initially empty tape and then halt. 
               The function S(n) (A060843) denotes the maximal number of steps (shifts) 
               which such a TM can do (it needs not produce many tape marks).
%C A028444 Given that 5-state machines can compute Collatz-like congruential functions 
               (see references under A060843), it may be very hard to find the next 
               term.
%C A028444 The sequence is non-computable.
%D A028444 John Hopcroft, Turing Machines, Sci. Amer. vol. 250, #5, 86-98, May 1984, 
               table on page 92 gives old lower bounds.
%D A028444 J. P. Jones, Recursive undecidability - an exposition, Amer. Math. Monthly, 
               81 (1974), 724-738.
%D A028444 H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the 
               EATCS, 40, pages 247-251, 1990.
%D A028444 Tibor Rado, On Noncomputable Functions, Bell System Technical Journal, 
               vol. 41, # 3, 877-884, May 1963.
%H A028444 H. Marxen, <a href="http://www.drb.insel.de/~heiner/BB/">Busy Beaver</
               a>
%H A028444 M. Somos, <a href="http://grail.cba.csuohio.edu/~somos/bb.html">Busy 
               Beaver Turing Machine</a>
%H A028444 M. Somos, <a href="http://grail.cba.csuohio.edu/~somos/busy.html">Busy 
               Beaver</a>
%H A028444 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 A028444 <a href="Sindx_Br.html#beaver">Index entries for sequences related to 
               Busy Beaver problem</a>
%Y A028444 Cf. A004147, A052200, A060843.
%Y A028444 Sequence in context: A133454 A061072 A130435 this_sequence A003973 A034747 
               A074165
%Y A028444 Adjacent sequences: A028441 A028442 A028443 this_sequence A028445 A028446 
               A028447
%K A028444 nonn,hard,nice
%O A028444 0,3
%A A028444 Scott Aaronson (sja8(AT)cornell.edu)
%E A028444 The next two terms are at least 4098 and 1.29*10^865.

Search completed in 0.001 seconds