A028444 Busy Beaver sequence, or Rado's sigma function: maximal number of 1's that an n-state Turing machine can print on an initially blank tape before halting.

0, 1, 4, 6, 13

Offset

0,3

Comments

Expanded definition from Daniel Forgues: Busy Beaver sequence, or Rado's Sigma function: maximum number of 1s that an n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) halting Turing machine can print on an initially blank tape (all 0's) before halting.

States q and q+ in set Q_n of n distinct states (plus the Halt state), tape symbols s and s+ in set S = {0, 1}, shift direction d+ in {LEFT, RIGHT} (NONE is excluded here), + suffix meaning next and q+ = f(q, s), s+ = g(q, s), d+ = h(q, s).

The function Sigma(n) = Sigma(n, 2) (A028444) denotes the maximal number of tape marks (1's) which a halting Turing Machine H with n internal states, 2 symbols, and a two-way infinite tape can produce onto an initially blank tape (all 0's) and then halt. The function S(n) = S(n, 2) (A060843) denotes the maximal number of steps (thus shifts, since direction NONE is excluded) which a halting machine H can take (not necessarily the same Turing machine producing a maximum number of 1's and need not even produce many tape marks). For all n, S(n) >= Sigma(n).

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

Rado's Sigma function grows faster than any computable function and is thus noncomputable.

From Daniel Forgues, Jun 05-06 2011: (Start)

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

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

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

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

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

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

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

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

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

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

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

References

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

Shallit, Jeffrey. A second course in formal languages and automata theory. Cambridge University Press, 2008. See Fig. 6.2, p. 185.

Links

Table of n, a(n) for n=0..4.

Bob Boonstra, Busy Beavers, Programmer's Challenge, MacTech Journal, Volume 16 (2000), Issue 9 - reports that in December 1984 George Uhing found a 5-state machine that produced 1915 1's before halting.

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

S. Ligocki, BB(6, 2) > 10↑↑15, 2022.

H. Marxen, Busy Beaver

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

Pascal Michel, Historical survey of Busy Beavers, 2011.

Pascal Michel, Behavior of busy beavers, 2010.

Pascal Michel, The Busy Beaver Competitions, 2010.

Pascal Michel, The Busy Beaver Competition: a historical survey, arXiv:0906.3749 [math.LO], 2009-2017.

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

Michael Somos, Busy Beaver Turing Machine.

Michael Somos, Busy Beaver.

Eric Weisstein's World of Mathematics, Busy Beaver

Index entries for sequences related to Busy Beaver problem

Crossrefs

Cf. A004147, A052200, A060843.

Keyword

nonn,hard,nice

Author

Scott Aaronson (sja8(AT)cornell.edu)

Extensions

The next two terms are at least 4098 and 10^^15.

Edited by Daniel Forgues, Mar 25 2010, Jun 05 2011

Edited by N. J. A. Sloane, Aug 30 2011

Status

approved

A016072 Obsolete sequence of lower bounds for A028444.

1, 4, 6, 13, 501, 2075

Offset

0,2

References

Dewdney, "The Armchair Universe," p. 164.

Links

Table of n, a(n) for n=0..5.

Keyword

nonn

Author

Robert G. Wilson v

Status

approved

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.

1, 6, 21, 107

Offset

1,2

Comments

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

The function Sigma(n) = Sigma(n, 2) (A028444) denotes the maximal number of tape marks (1's) 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 0's) 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 need not even produce many tape marks).

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.

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

From Daniel Forgues, Jun 05-06 2011: (Start)

A more precise definition might be as follows:

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.

Further comments:

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

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

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

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

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

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

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

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

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

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

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

a(6) > 10^^15, a tower of 10's of height 15 [Pavel Kropitz] - see Shawn Ligocki's blog. - N. J. A. Sloane, Jun 22 2022

References

A. H. Brady, 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).

J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010; see p. 33.

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.

Jeffrey Shallit, A second course in formal languages and automata theory. Cambridge University Press, 2008. See Fig. 6.2, p. 185.

Links

Table of n, a(n) for n=1..4.

Scott Aaronson, Who Can Name the Bigger Number?

Scott Aaronson, The busy beaver frontier, ACM SIGACT News 51.3 (2020): 32-54.

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

Bill Dubuque, Re: Halting is weak

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

Shawn Ligocki, BB(6,2) > 10^^15, Jun 21 2022.

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

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

H. Marxen, Busy Beaver Problem

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

Pascal Michel, Historical survey of Busy Beavers, 2011.

Pascal Michel, Behavior of busy beavers, 2010.

Pascal Michel, The Busy Beaver Competitions, 2010.

Pascal Michel, The Busy Beaver Competition: a historical survey, arXiv, 2010.

John Pavlus, How the Slowest Computer Programs Illuminate Math's Fundamental Limits, Quanta Magazine, Dec 10 2020.

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

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

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

Michael Somos, Busy Beaver Turing Machine

Michael Somos, Busy Beaver

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

The Busy Beaver Challenge

Eric Weisstein's World of Mathematics, Busy Beaver

Index entries for sequences related to Busy Beaver problem

Crossrefs

Cf. A028444, A362199.

Keyword

hard,nice,nonn,more

Author

Jud McCranie and N. J. A. Sloane, May 02 2001

Extensions

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

Edited by N. J. A. Sloane, Aug 30 2011

Additional links from Robert C. Lyons, Jun 22 2022

Status

approved

A052200 Number of n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) (halting or not) Turing machines.

1, 64, 20736, 16777216, 25600000000, 63403380965376, 232218265089212416, 1180591620717411303424, 7958661109946400884391936, 68719476736000000000000000000, 739696442014594807059393047166976, 9711967541295580042210555933809967104, 152784834199652075368661148843397208866816

Offset

0,2

Comments

T in T_(n, k) is a Turing machine with n states and k symbols;

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

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

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

+ suffix meaning next and q+ = f(q, s), s+ = g(q, s), d+ = h(q, s).

This sequence is computable. On the other hand, the busy beaver numbers are noncomputable, found only by examining each of the many n-state Turing machine programs' halting. - Michael Joseph Halm, Apr 29 2003

From Daniel Forgues, Jun 06 2011: (Start)

RE: Busy beaver halting Turing machines:

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

* (on a blank tape, all 0's, as input)

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

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

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

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

Cf. A028444 for Sigma(n, 2), A060843 for S(n, 2). (End)

Links

Table of n, a(n) for n=0..12.

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

Michael Somos, The Busy Beaver Problem

OEIS Wiki, Busy Beaver numbers

Index entries for sequences related to Busy Beaver problem

Formula

a(n) = (4*(n+1))^(2*n).

Example

a(1) = 64 = (4*1+4)^(2*1) = 8^2.

Mathematica

A052200[n_]:=(4(n+1))^(2n); Array[A052200, 20, 0] (* Paolo Xausa, May 21 2023 *)

Crossrefs

Cf. A028444, A004147, A060843.

Keyword

nonn,easy

Author

Michael Somos, Jan 28 2000

Extensions

Entry revised by N. J. A. Sloane, Feb 08 2007

Edited by Daniel Forgues, Mar 25 2010

Status

approved

A004147 Number of n-state Turing machines which halt. (Formerly M5233)

32, 9784, 7571840, 11140566368

Offset

1,1

Comments

This sequence is noncomputable, because it could be used to solve the halting problem. In fact, it is of the same degree of difficulty as the halting problem. - David Diamondstone (skeptical.scientist(AT)gmail.com), Dec 28 2007

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Table of n, a(n) for n=1..4.

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

H. Marxen, Busy Beaver

Michael Somos, Busy Beaver Turing Machine

Michael Somos, Busy Beaver

Index entries for sequences related to Busy Beaver problem

Crossrefs

Cf. A028444, A052200.

Keyword

nonn,nice,hard,bref

Author

N. J. A. Sloane

Extensions

More terms from David Diamondstone (skeptical.scientist(AT)gmail.com), Dec 28 2007

a(4) from Jonathan Lee, who enumerated all 25.6 billion 4-state machines up to 107 steps, Mar 05 2016

Status

approved

A353176 Maximum length of a finite snake in the Snake Number Problem with n-periodic instructions in an infinite square grid (see Comments).

30, 79, 152, 450, 241, 257, 1098, 1448, 9520, 8804, 8338, 11348, 25316, 18823

Offset

5,1

Comments

Given a list of n move instructions (up, right, down, left), the snake starts at the origin and moves according to the instructions, in order. If an instruction tells it to move to a square that has already been visited, the snake skips that instruction. After it has followed (or skipped) the last instruction in the list, it starts again with the first one. The snake is either finite (if it gets stuck at some point) or infinite (if it can go on forever). a(n) is the maximum number of squares visited by a finite snake. For n <= 4, all snakes are infinite. - Pontus von Brömssen, May 08 2022

Links

Table of n, a(n) for n=5..18.

Ariel Futoransky, Snake Program, Snake Program to try the snakes, April 2022 (see bottom animation and label for different options).

Rodolfo Kurchan, Puzzle Fun, Snake Number Problem, March 2022.

Example

a(5) = 30
URDDL: 30
-- -- 20 21 -- --
-- 18 19 22 23 --
16 17 02 03 24 --
15 14 01 04 25 26
12 13 06 05 30 27
11 10 07 -- 29 28
-- 09 08 -- -- --
.
a(6) = 79
UURDLL: 79
-- -- -- -- -- -- -- 74 75 -- --
-- -- -- -- -- 69 70 73 76 77 --
-- -- -- 64 65 68 71 72 79 78 --
-- -- -- 63 66 67 -- 27 28 -- --
-- -- 61 62 -- 22 23 26 29 30 --
56 57 60 17 18 21 24 25 32 31 --
55 58 59 16 19 20 03 04 33 34 --
54 53 52 15 14 13 02 05 06 35 36
-- -- 51 -- -- 12 01 08 07 38 37
-- -- 50 49 48 11 10 09 40 39 --
-- -- -- -- 47 -- 43 42 41 -- --
-- -- -- -- 46 45 44 -- -- -- --
.
   n | Number of finite solutions | Maximum length | Instructions that give
     |         A352388(n)         |      a(n)      |   the maximum length
  -------------------------------------------------------------------------
   5                    5                  30         URDDL
   6                   21                  79         UURDLL
   7                  127                 152         URULLDD
   8                  618                 450         URURUULD
   9                 2934                 241         URRRRDLRR
  10                13542                 257         URRLDLRRUR
  11                61803                1098         URUURUUULLD
  12               276650                1448         URUULLDUDDDD
  13              1219508                9520         URRRLLDLRRULL
  14              5309179                8804         URRURRRLDLRULL
  15             22868295                8338         UDDRULUUUULLULD
  16             97663066               11348         URRURRRLDDLRUULL
  17            414156142               25316         URRRDLULUUUUULURL
  18           1746438478               18823         UDDDRULULLULLUULDU
Computer solutions a(5) to a(13) found by Giorgio Vecchi.
Computer solutions a(14) to a(18) found by Ariel Futoransky.

Crossrefs

Cf. A352388, A353259, A353060, A028444.

Keyword

nonn,more

Author

Rodolfo Kurchan, Apr 28 2022

Status

approved

A333479 Busy Beaver for lambda calculus: the maximum normal form size of any closed lambda term of size n, or 0 if no closed term of size n exists.

0, 0, 0, 4, 0, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 24, 26, 30, 42, 52, 44, 58, 223, 160, 267, 298, 1812, 327686, 38127987424941, 578960446186580977117854925043439539266349923328202820197287920039565648199686

Offset

1,4

Comments

Sizes of terms are defined as in Binary Lambda Calculus (see Lambda encoding link) by size(lambda M)=2+size(M), size(M N)=2+size(M)+size(N), and size(V)=1+i for a variable V bound by the i-th enclosing lambda.

a(34), a(35) and a(36) correspond to Church numerals 2^2^2^2, 3^3^3, and 2^2^2^3, where numeral n has size 5*n+6.

a(38) > 10^19729, corresponding to Church numeral 2^2^2^2^2.

Only a finite number of entries can be known, as the function is uncomputable.

Quoting from Chaitin's paper below: "to information theorists it is clear that the correct measure is bits, not states [...] to deal with Sigma(number of bits) one would need a model of a binary computer as simple and compelling as the Turing machine model, and no obvious natural choice is at hand."

a(63) > Graham's number, as shown in the Googology Wiki article in the links. - John Tromp, Apr 11 2023

A universal form of this Busy Beaver, using the binary input feature of Binary Lambda Calculus, is given in sequence A361211. - John Tromp, May 24 2023

References

Gregory Chaitin, Computing the Busy Beaver Function, in T. M. Cover and B. Gopinath, Open Problems in Communication and Computation, Springer, 1987, pages 108-112.

John Tromp, Binary Lambda Calculus and Combinatory Logic, in Randomness And Complexity, from Leibniz To Chaitin, ed. Cristian S. Calude, World Scientific Publishing Company, October 2008, pages 237-260.

Links

Table of n, a(n) for n=1..36.

Googology Wiki, The largest number representable in 64 bits.

MathOverflow, What's the smallest lambda-calculus term not known to have a normal form?, 2020.

John Tromp, Lambda encoding

John Tromp, Haskell program for analyzing Busy Beaver numbers

John Tromp, program output analysis

Index entries for sequences related to Busy Beaver problem

Example

The smallest closed lambda term is lambda x.x with encoding 0010 of size 4, giving a(4)=4, as it is in normal form. There is no closed term of size 5, so a(5)=0. a(21)=22 because of term (lambda x. x x) (x (lambda y. x)).

Crossrefs

Cf. A028444, A114852, A195691, A333958, A361211.

Keyword

nonn

Author

John Tromp, Mar 23 2020

Extensions

a(33)-a(34) from John Tromp, Apr 10 2020

a(35) from John Tromp, Apr 18 2020

a(36) from John Tromp, Apr 19 2020

Status

approved

A081419 Largest value held in any register at the end of a halting computation by an n-instruction register Minski machine.

0, 1, 2, 3, 4, 6, 9, 34, 520

Offset

1,3

Comments

We start with initially empty registers and include exactly one Halt instruction. Analogous to the Busy Beaver function, Sigma, for Turing Machines.

n<=5 are proved. 5<n<=9 are good lower bounds.

References

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

Links

Table of n, a(n) for n=1..9.

Formula

Noncomputable.

Example

E.g. B(3) is of the form:
1: A+ -> 2
2: A+ -> 3
3: Halt
Halting with B(3)=2

Crossrefs

Cf. A028444.

Keyword

hard,nice,nonn

Author

Rick J. Griffiths (rjg42(AT)cam.ac.uk), Apr 20 2003

Status

approved

A164278 a(n) = (6*n + 1)^(2*n) - 1.

0, 48, 28560, 47045880, 152587890624, 819628286980800, 6582952005840035280, 73885357344138503765448, 1104427674243920646305299200, 21209401372879911350250244140624, 508858109619679129936596364708525200

Offset

0,2

Comments

In Bátfai's notation, a(n) gives the total number of Turing machines with n states.

Links

Table of n, a(n) for n=0..10.

Norbert Bátfai, On the Running Time of the Shortest Programs, arXiv:0908.1159 [cs.CC], Aug 10, 2009.

Mathematica

Table[(6n+1)^(2n)-1, {n, 0, 20}] (* Harvey P. Dale, Dec 24 2021 *)

Prog

(Maxima) makelist((6*n + 1)^(2*n) - 1, n, 0, 20); /* Franck Maminirina Ramaharo, Jan 15 2019 */

Crossrefs

Cf. A028444.

Keyword

easy,nonn

Author

Jonathan Vos Post, Aug 11 2009

Extensions

Edited and name clarified by Franck Maminirina Ramaharo, Jan 15 2019

Status

approved

A118874 A halting sequence: let f_n be the n-th recursive function, relative to the Godel numbering given in Cutland, then a(n) is f_n(n)+1 if the corresponding program halts on input n, 0 otherwise.

1, 3, 1, 4, 2, 1, 1, 0, 1, 12, 2, 1, 1, 1, 1, 16, 0, 19, 1, 21, 3, 2, 2, 0, 1, 1, 1, 1, 1, 1, 1, 32, 1, 0, 0, 36, 2, 1, 1, 0, 2, 45, 3, 2, 2, 2, 2, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 64, 1, 67, 1, 0, 0, 0, 0, 0, 1, 76, 2, 1, 1, 1, 1, 81, 0, 84, 2, 86, 4, 3, 3, 0, 2, 2, 2, 2, 2, 2, 2, 1, 1, 0, 0

Offset

0,2

Comments

The prototypical example of a noncomputable sequence.

References

Nigel Cutland, "Computability: An introduction to recursive function theory". Cambridge University Press, 1980. p. 78.

Links

Table of n, a(n) for n=0..98.

Ramin Naimi, URM Simulator

Example

Using Cutland's Godel numbering, 80 corresponds to the URM program "Z(1) J(1,1,1) S(1)", which clearly loops forever on any input, so a(80)=0. On the other hand, 17 corresponds to the URM program "S(1) T(1,1)", which, on input 17, produces 18. So a(17)=18+1=19.

Crossrefs

Cf. A004147, A028444, A052200, A060843, A081419.

Keyword

nonn

Author

Sam Alexander, May 24 2006

Status

approved