0,3

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).

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.

The sequence is non-computable.

John Hopcroft, Turing Machines, Sci. Amer. vol. 250, #5, 86-98, May 1984, table on page 92 gives old lower bounds.

J. P. Jones, Recursive undecidability - an exposition, Amer. Math. Monthly, 81 (1974), 724-738.

H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, 1990.

Tibor Rado, On Noncomputable Functions, Bell System Technical Journal, vol. 41, # 3, 877-884, May 1963.

H. Marxen, Busy Beaver

M. Somos, Busy Beaver Turing Machine

M. Somos, Busy Beaver

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

Index entries for sequences related to Busy Beaver problem

Cf. A004147, A052200, A060843.

Adjacent sequences: A028441 A028442 A028443 this_sequence A028445 A028446 A028447

Sequence in context: A133454 A061072 A130435 this_sequence A003973 A034747 A074165

nonn,hard,nice

Scott Aaronson (sja8(AT)cornell.edu)

The next two terms are at least 4098 and 1.29*10^865.