This site is supported by donations to The OEIS Foundation.

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A060843 Busy Beaver problem: a(n) = maximal number of steps that an n-state Turing machine can make on an initially blank tape before eventually halting. 7

%I

%S 1,6,21,107

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

%C "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.]

%C The function Sigma(n) = Sigma(n, 2) (A028444) denotes the maximal number of tape marks (1s) that a Turing Machine with n internal states (plus the Halt state,) 2 symbols, and a two-way infinite tape can write on an initially blank tape (all 0s) 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 needs not even produce many tape marks.)

%C Given that 5-state 2-symbol halting Turing machines can compute Collatz-like congruential functions (see references), it may be very hard to find the next term.

%C The sequence grows faster than any computable function of n and so is noncomputable.

%C From _Daniel Forgues_, Jun 05-06 2011: (Start)

%C A more precise definition might be as follows:

%C Busy Beaver Problem: a(n) is the maximal number of steps that an n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) Turing machine can make on an initially blank tape and then halt.

%C H in H_(n, k) is a halting* Turing machine with n states and k symbols;

%C * (on a blank tape (all 0s) as input)

%C States q, q+ in set Q_n of n distinct states (plus the Halt state;)

%C Symbols s, s+ in set S_k of k distinct symbols (0 as the blank symbol;)

%C Shift direction d+ in {LEFT, RIGHT} (NONE is excluded here;)

%C sigma(H) is the number of non-blank symbols left on the tape by H;

%C s(H) is the number of steps (or shifts in our case) taken by H;

%C Sigma(n, k) = max {sigma(H) : H is a halting Turing machine with n states and k symbols}

%C S(n, k) = max {s(H) : H is a halting Turing machine with n states and k symbols}

%C a(n) is S(n) = S(n, 2) since a 2-symbol BB-class Turing machine is assumed.

%C For all n, S(n, k) >= Sigma(n, k), k >= 2. (End)

%D 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 J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010; see p. 33.

%D Shen Lin and T. Rado, Computer Studies of Turing Machine Problems, J. ACM 12 (1965), 196-212.

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

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

%D Rado, T., On Non-Computable Functions, Bell System Technical J. 41 (1962), 877-884.

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

%D 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 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 Claude E. Shannon, A universal Turing machine with two internal states, Automata Studies, Ann. of Math. Stud. 34 (1956) 157-165.

%H Scott Aaronson, <a href="http://www.scottaaronson.com/writings/bignumbers.html">Who Can Name the Bigger Number?</a>

%H A. H. Brady, <a href="https://doi.org/10.1090/S0025-5718-1983-0689479-6">The determination of Rado's noncomputable function Sigma(k) for four-state Turing machines</a>, Math. Comp. 40 #62 (1983) 647-665.

%H Bill Dubuque, <a href="http://groups.google.com/groups?selm=WGD.96Feb13081831%40berne.ai.mit.edu">Re: Halting is weak</a>

%H Daniel Forgues, <a href="http://oeis.org/wiki/Busy_Beaver_numbers">Busy Beaver numbers</a>

%H 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 H. Marxen, <a href="http://www.drb.insel.de/~heiner/BB/">Busy Beaver Problem</a>

%H Pascal Michel, <a href="http://www.logique.jussieu.fr/~michel/ha.html">Historical survey of Busy Beavers</a>, 2011.

%H Pascal Michel, <a href="http://www.logique.jussieu.fr/~michel/beh.html">Behavior of busy beavers</a>, 2010.

%H Pascal Michel, <a href="http://www.logique.jussieu.fr/~michel/bbc.html">The Busy Beaver Competitions</a>, 2010.

%H Pascal Michel, <a href="http://arxiv.org/abs/0906.3749">The Busy Beaver Competition: a historical survey</a>, arXiv, 2010.

%H M. Somos, <a href="http://grail.cba.csuohio.edu/~somos/bb.html">Busy Beaver Turing Machine</a>

%H M. Somos, <a href="http://grail.cba.csuohio.edu/~somos/busy.html">Busy Beaver</a>

%H Q. F. Stout, <a href="http://www.eecs.umich.edu/~qstout/abs/busyb.html">The Complex Behavior of Simple Machines</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BusyBeaver.html">Busy Beaver</a>

%H <a href="/index/Br#beaver">Index entries for sequences related to Busy Beaver problem</a>

%Y Cf. A028444.

%K hard,nice,nonn

%O 1,2

%A _Jud McCranie_ and _N. J. A. Sloane_, May 02 2001

%E The next two terms are at least 47176870 and 7.4*10^36534.

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

%E Edited by _N. J. A. Sloane_, Aug 30 2011

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified January 18 03:13 EST 2019. Contains 319260 sequences. (Running on oeis4.)