Busy beaver - Knowledge

5145: 5250: 214: 4958: 6583: 6974:(4) = 107. Brady defines two new categories for non-halting 3-state 2-symbol Turing Machines: Christmas Trees and Counters. He uses a computer program to prove that all but 27 machines which run over 107 steps are variants of Christmas Trees and Counters which can be proven to run infinitely. The last 27 machines (referred to as holdouts) are proven by personal inspection by Brady himself not to halt. 4767:), and several other busy beaver functions. In this table, 2-symbol Turing machines are used. Entries listed as "?" are at least as large as other entries to the left (because all n-state machines are also (n+1) state machines), and no larger than entries above them (because S(n) ≥ space(n) ≥ Σ(n) ≥ num(n)). So, space(6) is known to be greater than 10⇈15, as space(n) ≥ Σ(n) and Σ(6) > 10⇈15. 5656: 5644: 5632: 1315: 5620: 47: 5694: 5682: 5670: 143: 88: 449:"Running" the machine consists of starting in the starting state, with the current tape cell being any cell of a blank (all-0) tape, and then iterating the transition function until the Halt state is entered (if ever). If, and only if, the machine eventually halts, then the number of 1s finally remaining on the tape is called the machine's 5706: 254:

states and eventually halts. Such machines are assumed to start on a blank tape, and the tape is assumed to contain only zeros and ones (a binary Turing machine). A player should conceive of a set of transitions between states aiming for the highest score or longest running time while making sure the

7242:

Cf Chapter 9, Turing Machines. A difficult book, meant for electrical engineers and technical specialists. Discusses recursion, partial-recursion with reference to Turing Machines, halting problem. A reference in Booth attributes busy beaver to Rado. Booth also defines Rado's busy beaver problem in

5605:

In the following table, the rules for each busy beaver (maximizing Σ) are represented visually, with orange squares corresponding to a "1" on the tape, and white corresponding to "0". The position of the head is indicated by the black ovoid, with the orientation of the head representing the state.

4963:

The diagram is compressed so only steps which change the tape are shown. Green and yellow triangles indicate regions where the Turing machine shuttles back and forth; the time taken is proportional to the areas of these colored triangles. The bottom row is an excerpt of the tape and the read/write

245:

Turing machines consist of an infinite tape, and a finite set of states which serve as the program's "source code". Producing the most output is defined as writing the largest number of 1s on the tape, also referred to as achieving the highest score, and running for the longest time is defined as

949:

whether an arbitrary Turing machine is a busy beaver. (Such an algorithm cannot exist, because its existence would allow Σ to be computed, which is a proven impossibility. In particular, such an algorithm could be used to construct another algorithm that would compute Σ as follows: for any given

6584:"Heiner Marxen and Jürgen Buntrock. Attacking the busy beaver 5. Bulletin of the European Association for Theoretical Computer Science, no. 40 (Feb.1990), pp. 247–251. - Pascal Michel. Busy beaver competition and Collatz-like problems. Archive for mathematical logic, vol. 32 (1993), pp. 351–367" 873:

shift directions uniformly, and a fourth by reversing the halt direction of the all-swapped busy beaver. Furthermore, a permutation of all states except Start and Halt produces a machine that attains the same score. Theoretically, there could be more than one kind of transition leading to the

3173:

In 1964 Milton Green developed a lower bound for the 1s-counting variant of the Busy Beaver function that was published in the proceedings of the 1964 IEEE symposium on switching circuit theory and logical design. Heiner Marxen and Jürgen Buntrock described it as "a non-trivial (not primitive

3502:

Specifically, the lower bound was shown with a series of recursive Turing machines, each of which was made of a smaller one with two additional states that repeatedly applied the smaller machine to the input tape. Defining the value of the N-state busy-beaver competitor on a tape containing

2478:

by looking for the system with the most states across all branches or the branch with the longest number of steps. The question of whether a given NDTM will halt is still computationally irreducible, and the computation required to find an NDTM busy beaver is significantly greater than the

4995:

In the tables, columns represent the current state and rows represent the current symbol read from the tape. Each table entry is a string of three characters, indicating the symbol to write onto the tape, the direction to move, and the new state (in that order). The halt state is shown as

1977:

Analogs of the shift function can be simply defined in any programming language, given that the programs can be described by bit-strings, and a program's number of steps can be counted. For example, the busy beaver game can also be generalized to two dimensions using Turing machines on

645:(i.e., visit) before halting. This includes the starting square, but not a square that the machine only reaches after the halt transition (if the halt transition is annotated with a move direction), because that square does not influence the machine's behaviour. This is the maximal 2582:). Write a computer program that sequentially tests this conjecture for increasing values. In the case of Goldbach's conjecture, we would consider every even number ≥ 4 sequentially and test whether or not it is the sum of two prime numbers. Suppose this program is simulated on an 2613:) steps, the machine does not halt, we know that it never will and thus that there are no counterexamples to the given conjecture (i.e., no even numbers that are not the sum of two primes). This would prove the conjecture to be true. Thus specific values (or upper bounds) for 1258:(3) = 21, then to simulate all the essentially different 3-state machines for up to 21 steps. By analyzing the behavior of the machines that had not halted within 21 steps, they succeeded in showing that none of those machines would ever halt, thus proving the conjecture that 1663:) can also be established by reference to the blank tape halting problem. The blank tape halting problem is the problem of deciding for any Turing machine whether or not it will halt when started on an empty tape. The blank tape halting problem is equivalent to the standard 7024:

Machlin and Stout describe the busy beaver problem and many techniques used for finding busy beavers (which they apply to Turing Machines with 4-states and 2-symbols, thus verifying Brady's proof). They suggest how to estimate a variant of Chaitin's halting probability

484:

This Turing machine would move to the right, swapping the value of all the bits it passes. Since the starting tape is all 0s, it would make an unending string of ones. This machine would not be a busy beaver contender because it runs forever on a blank tape.

3154:

within size constraints, (2) their ability to perform non-trivial calculations before halting, and (3) the difficulty in finding and proving these machines; these features suggest that Busy Beaver machines possess the necessary complexity for universality.

7419:

This is the description of ideas, of the algorithms and their implementation, with the description of the experiments examining 5-state and 6-state Turing machines by parallel run on 31 4-core computer and finally the best results for 6-state

977:

for which it is possible to obtain its values and prove that they are correct. It is not hard to show that Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, and with progressively more difficulty it can be shown that Σ(3) = 6, Σ(4) = 13 and Σ(5) = 4098 (sequence

4604: 2586:-state Turing machine. If it finds a counterexample (an even number ≥ 4 that is not the sum of two primes in our example), it halts and indicates that. However, if the conjecture is true, then our program will never halt. (This program halts 1246:) steps, at which point any machine that hasn't yet halted will never halt. At that point, by observing which machines have halted with the most 1s on the tape (i.e., the busy beavers), one obtains from their tapes the value of Σ( 3280: 7100:

Green recursively constructs machines for any number of states and provides the recursive function that computes their score (computes σ), thus providing a lower bound for Σ. This function's growth is comparable to that of

1978:

two-dimensional tapes, or to Turing machines that are allowed to stay in the same place as well as move to the left and right. Alternatively a "busy beaver function" for diverse models of computation can be defined with

733: 237:

program producing infinite output or running for infinite time is easily conceived, such programs are excluded from the game. Rather than traditional programming languages, the programs used in the game are n-state

4184: 6924:(3) = 21 by proving that all 3-state 2-symbol Turing Machines which don't halt within 21 steps will never halt. (Most are proven automatically by a computer program, however 40 are proven by human inspection.) 1187:

Because normal Turing machines are required to have a shift in each and every transition or "step" (including any transition to a Halt state), the max-shifts function is at the same time a max-steps function.

1211:). Each shift may write a 0 or a 1 on the tape, while Σ counts a subset of the shifts that wrote a 1, namely the ones that hadn't been overwritten by the time the Turing machine halted; consequently, 4961:

A zoomed-out space-time diagram of the 5-state busy beaver machine (for S(n), then Σ(n)). The machine runs for 47,176,870 steps, peaking with 12288 zeroes, and leaving behind 4098 zeroes upon halt.

4093:

Trivially, S(n) ≥ Σ(n) because a machine that writes Σ(n) ones must take at least Σ(n) steps to do so. It is possible to give a number of upper bounds on the time S(n) with the number of ones Σ(n):

1928: 802: 327:

for each number and halt on a counterexample: if this machine had not halted after running for S(27) steps, then it must run forever, resolving the conjecture. Many other problems, including the

4309: 3435: 2721: 2651:

The values of S(n) and the other busy beaver functions get very large, very quickly. While the value of S(5) is only around 47 million, the value of S(6) is more than 10⇈15, which is equal to

3776: 1840: 3150:, a conjecture was proposed in 2012 suggesting that Busy Beaver machines were natural candidates for Turing universality as they display complex characteristics, known for (1) their maximal 4083: 916: 4370: 4432: 3983: 1289:). Stefan O'Rear then reduced it to 1919 states, with the dependency on the stationary Ramsey property eliminated, and later to 748 states. In July 2023, Riebel reduced it to 745 states. 3468: 493:

In his original 1962 paper, Radó defined two functions related to the busy beaver game: the score function Σ(n) and the shifts function S(n). Both take a number of Turing machine states

319:

in his 1962 paper, "On Non-Computable Functions". One of the most interesting aspects of the busy beaver game is that, if it were possible to compute the functions Σ(n) and S(n) for all

4787:() and S(n) ≥ space(n). 4098 is an upper bound for num(5), because Σ(5) = 4098 () and Σ(n) ≥ num(n). The last entry listed as "?" is num(6), because Σ(6) > 10⇈15, but Σ(n) ≥ num(n). 4488: 4934:

The 5-state busy beaver was discovered by Heiner Marxen and Jürgen Buntrock in 1989, but only proved to be the winning fifth busy beaver — stylized as BB(5) — in 2024 using a proof in

3890: 533:-state Turing machine can output before halting, while the shifts function S(n) gives the maximum number of shifts (or equivalently steps, because each step includes a shift) that an 3339: 2942:. If the theory is inconsistent, then all false statements are provable, and the Turing machine can be given the condition to halt if and only if it finds a proof of, for example, 4233: 2524:. Theoretically speaking, the value of S(n) encodes the answer to all mathematical conjectures that can be checked in infinite time by a Turing machine with less than or equal to 560:

A number of other uncomputable functions can also be defined based on measuring the performance of Turing machines in other ways than time or maximal number of ones. For example:

7037: 5606:

Individual tapes are laid out horizontally, with time progressing from top to bottom. The halt state is represented by a rule which maps one state to itself (head doesn't move).

557:, because they each grew faster than any computable function. The function BB(n) has been defined to be either of these functions, so that notation is not used in this article. 2723:

with a stack of 15 tens. This number has 10⇈14 digits and is unreasonable to use in a computation. The value of S(27), which is the number of steps the current program for the

1967: 1794: 1732: 639: 1871: 1763: 593: 4743: 2727:

would need to be run to give a conclusive answer, is incomprehensibly huge, and not remotely possible to write down, much less run a machine for, in the observable universe.

2076: 3677: 2561: 2818: 323:, then this would resolve all mathematical conjectures which can be encoded as "does this Turing machine halt or not". For example, a 27-state Turing machine could check 217:

This "space-time diagram" shows the first 100,000 timesteps of the best 5-state busy beaver from top to bottom. Orange is "1", white is "0" (image compressed vertically).

4670: 4511: 3628: 3497: 3313: 3359: 3557: 3002: 2112: 106: 2186: 2014: 2853: 735:. More functions can also be defined by operating the game on different computing machines, such as 3-symbol Turing machines, non-deterministic Turing machines, the 7382:

This article contains a complete classification of the 2-state, 3-symbol Turing machines, and thus a proof for the (2, 3) busy beaver: Σ(2, 3) = 9 and S(2, 3) = 38.

3088: 3061: 2920: 2785: 4703: 4637: 3808: 3583: 2966: 3521: 3034: 2940: 2893: 2873: 2758: 2226: 2206: 2152: 2132: 2034: 551: 531: 513:

and output the maximum score attainable by a Turing machine of that number of states by some measure. The score function Σ(n) gives the maximum number of 1s an

511: 5711:

Evolution of 4-state busy beaver until halt. Bottom line in left image wraps to top line of right image. The final step writes "1" before halting (not shown).

3192: 1195:

is noncomputable for the same reason that Σ is noncomputable — it grows faster than any computable function. He proved this simply by noting that for each

6920:

The results of this paper had already appeared in part in Lin's 1963 doctoral dissertation, under Radó's guidance. Lin & Radó prove that Σ(3) = 6 and

1076: 6475:

Tristan Stérin and Damien Woods (July 2021). On the hardness of knowing busy beaver values BB(15) and BB(5,4) (Technical Report). Maynooth University.

985: 746: 6256:

Adam Yedidia and Scott Aaronson (May 2016). A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory (Technical Report). MIT.

660: 7567: 6846: 5862: 5597:

1 1 1 ... 1 1 1 ("10" followed by more than 10↑↑15 contiguous "1"s in more than 10↑↑15 steps, where 10↑↑15=10, an exponential tower of 15 tens).

7207:

Wherein Brady (of 4-state fame) describes some history of the beast and calls its pursuit "The Busy Beaver Game". He describes other games (e.g.

2483:

cases or rules, the table to the right gives the maximum number of steps before halting and maximum number of unique states created by the NDTM.

874:

halting state, but in practice it would be wasteful, because there is only one sequence of state transitions producing the sought-after result.)

7243:"home problems" 3, 4, 5, 6 of Chapter 9, p. 396. Problem 3 is to "show that the busy beaver problem is unsolvable... for all values of n." 276:-state busy beaver game. Depending on definition, it either attains the highest score, or runs for the longest time, among all other possible 7401: 7233: 7198: 7165: 6445: 4099: 3005: 2605:) we can decide (in a finite amount of time) whether or not it will ever halt by simply running the machine that many steps. And if, after 233:

of a given size that (depending on definition) either produces the most output possible, or runs for the longest number of steps. Since an

6874:

This is where Radó first defined the busy beaver problem and proved that it was uncomputable and grew faster than any computable function.

6286: 5813: 1025: 5913: 2875:. This implies that for each theory there is a specific largest value of S(n) that it can prove. This is true because for every such 1406: 200: 182: 124: 74: 7462:) at the Rensselaer RAIR Lab. This effort found several new records and established several values for the quadruple formalization. 5675:

Evolution of 1-state busy beaver until halt. The initial state triggers a halt, with a single "1" being written before termination.

1079:

is illustrated by this result: in an axiomatic system of ordinary mathematics, there is a true-but-unprovable sentence of the form

2231:

The longest running 6-state, 2-symbol machine which has the additional property of reversing the tape value at each step produces

1687:) steps; if it has still not halted, it never will. So, since the blank tape halting problem is not computable, it follows that 7137: 1277:. To do so they constructed a 7910-state Turing machine whose behavior cannot be proven based on the usual axioms of set theory ( 7254: 7150: 6430: 1278: 332: 2475: 962:-state busy beaver is found; this busy beaver machine would then be simulated to determine its score, which is by definition Σ( 312: 7557: 7473: 1876: 1340: 869:-state busy beaver, another is obtained by merely changing the shift direction in a halting transition, a third by reversing 440:

a direction to move (left or right; that is, shift to the tape cell one place to the left or right of the current cell), and

303:. In fact, both the functions Σ(n) and S(n) eventually become larger than any computable function. This has implications in 3174:

recursive) lower bound". This lower bound can be calculated but is too complex to state as a single expression in terms of

2628:

It is extremely hard to prove values for the busy beaver function (and the max shift function). Every known exact value of

7552: 6854: 5870: 1387: 1075:; consequently, in the context of ordinary mathematics, neither the value nor any upper-bound of Σ(10⇈10) can be proven. ( 771: 7459: 7046: 4240: 3368: 2654: 3362: 1359: 1336: 1072: 222: 60: 7320: 7259: 3683: 2509: 1799: 1067:

were proven). As mentioned in the cited reference, for any axiomatic system of "ordinary mathematics" the least value

6768: 2479:

deterministic case, since there are multiple branches that need to be considered. For a 2-state, 2-color system with

1675:) was computable, then we could solve the blank tape halting problem simply by running any given Turing machine with 3999: 885: 6940: 6039: 4329: 1366: 6366: 4376: 3897: 3440: 437:

a symbol to write over the symbol in the current tape cell (it may be the same symbol as the symbol overwritten),

6645:

Proceedings of the 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design

4438: 3781:

This leads to two formulas, for odd and even numbers, for calculating the lower bound given by the Nth machine,

3129:

A 15-state Turing machine has been constructed that halts if and only if the following conjecture formulated by

7469: 3151: 1601:) 1s on tape, and at last it will clear all 1s and then halt. But the phase of cleaning will continue at least 1325: 160: 153: 7212: 5249: 5144: 3816: 3121: 2724: 2579: 324: 2624:

However, current results on the busy beaver problem suggest that this will not be practical for two reasons:

1373: 280:-state competing Turing machines. The functions determining the highest score or longest running time of the 7562: 7102: 4951: 4947: 3318: 2274:

as the largest number which can be present in any register on halting, for a given number of instructions.

1344: 1329: 808:) is the maximum attainable score (the maximum number of 1s finally on the tape) among all halting 2-symbol 250:

state busy beaver game consists of finding the longest-running or highest-scoring Turing machine which has

7369: 7329: 7268: 6048: 4494:

Ben-Amram and Petersen, 2002, also give an asymptotically improved bound on S(n). There exists a constant

4191: 758: 757:

The score function quantifies the maximum score attainable by a busy beaver on a given measure. This is a

554: 7074:

and describe in detail the method they used to find these machines and prove many others will never halt.

6176: 2740:

can prove all of the function's values. Specifically, given a computable and arithmetically sound theory

477:

In state 1, if the current symbol is 0, write a 1, move one space to the right, and transition to state 1

7215:). Of particular interest is "The Busy Beaver Game in Two Dimensions" (p. 247). With 19 references. 6824: 3178:. This was done with a set of Turing machines, each of which demonstrated the lower bound for a certain 1979: 1355: 1215:

grows at least as fast as Σ, which had already been proved to grow faster than any computable function.

1020:

is the smallest number of states needed for a BB-class Turing machine that halts with a single block of

1009: 7366:

Computation and Logic in the Real World, Proceedings of the Third Conference on Computability in Europe

1941: 1796:

by noting that every tape square a Turing machine writes a one to, it must also visit: in other words,

1768: 1706: 613: 3146:

Exploring the relationship between computational universality and the dynamic behavior of Busy Beaver

480:

In state 1, if the current symbol is 1, write a 0, move one space to the right, and transition to HALT

7085: 6995: 6267: 4320: 3009: 1845: 1737: 567: 304: 7374: 7334: 4712: 3090:

prove the consistency of those below them, placing all such theories on a countably infinite scale.

2039: 7273: 7116: 5466:

Note in the image to the right how this solution is similar qualitatively to the evolution of some

4599:{\displaystyle S(n)\leq \Sigma \left(n+\left\lceil {\frac {8n}{\log _{2}n}}\right\rceil +c\right).} 942: 919: 762: 600: 7437:, who, with Jürgen Buntrock, found the above-mentioned records for a 5 and 6-state Turing machine. 6885: 4319:-state Turing machine is allowed to output contiguously, rather than in any position (the largest 3634: 2534: 1265:

In 2016, Adam Yedidia and Scott Aaronson obtained the first (explicit) upper bound on the minimum

1104:

In addition to the function Σ, Radó introduced another extreme function for Turing machines, the

7347: 7286: 6959: 6909: 6890: 6818: 6611: 6521: 6476: 6257: 6238: 3990: 3112: 2790: 2567: 386:

states is distinguished as the starting state. (Typically, the states are labelled by 1, 2, ...,

328: 7318:

Ben-Amram, A. M.; Petersen, H. (2002). "Improved Bounds for Functions Related to Busy Beavers".

5009:

with an infinite tape that contains all 0s. Thus, the initial symbol read from the tape is a 0.

4646: 3591: 3473: 3289: 7455: 7189:

Brady, Allen H. (1995). "The Busy Beaver Game and the Meaning of Life". In Herken, Rolf (ed.).

3344: 7512: 7397: 7229: 7208: 7194: 7161: 7129: 7111: 6986: 6722: 6603: 6560: 6441: 6103: 5985: 5467: 3526: 2971: 2497: 2081: 553:-state Turing machine can undergo before halting. He proved that both of these functions were 213: 7086:

1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design

2157: 1985: 599:

ones a halting Turing machine can write on a blank tape. In other words, this is the largest

7339: 7278: 7089: 7011: 7003: 6949: 6899: 6863: 6714: 6648: 6595: 6552: 6513: 6228: 6095: 5977: 5879: 5724: 3124:

is false, and a 27-state machine for that conjecture has been proposed but not yet verified.

2823: 2737: 2271: 1029: 646: 230: 66: 31: 3066: 3039: 2898: 2763: 2290:= 3 symbols would have the symbols 0, 1, and 2. The generalization to Turing machines with 1508:

1s on an initially blank tape. This machine may be constructed in a trivial manner to have

7221: 7146: 6569: 6426: 6172: 4679: 4613: 3784: 3147: 1664: 1286: 1282: 736: 308: 6540: 3562: 2945: 2640:-state Turing machine and proving whether or not each halts. One would have to calculate 1380: 6999: 6271: 4957: 7485: 7390: 6867: 6744: 6367:"GitHub - sorear/metamath-turing-machines: Metamath proof enumerators and other things" 5883: 4935: 3506: 3100: 3019: 2925: 2878: 2858: 2743: 2621:) could be, in theory, used to systematically solve many open problems in mathematics. 2571: 2512:

could in theory, but not in practice, be solved in a systematic way given the value of

2211: 2191: 2137: 2117: 2019: 1455:

denote a Turing machine cleaning the sequence of 1s initially written on the tape. Let

1033: 536: 516: 496: 367: 239: 164: 7294: 6954: 6931: 3275:{\displaystyle \Sigma (8)\geq 3\times (7\times 3^{92}-1)/2\approx 8.248\times 10^{44}} 7546: 7504: 7007: 6881: 6842: 6556: 6496: 5858: 3130: 363: 336: 316: 7351: 7290: 6913: 6242: 5748: 1636:) may be proved in a similar way. In the above proof, one must exchange the machine 7114:(1984). "A computer trap for the busy beaver, the hardest working Turing machine". 6517: 300: 234: 35: 7536: 6413: 812:-state Turing machines of the above-described type, when started on a blank tape. 7441: 7171: 6451: 3008:. This can be used to place various theories on a scale, for example the various 2736:

Another property of S(n) is that no arithmetically sound, computably axiomatized

641:

is defined to be the maximal number of tape squares a halting Turing machine can

7515: 6981: 5782: 5238:

Unlike the previous machines, this one is a busy beaver only for Σ, but not for

3111:

A 744-state Turing machine has been constructed that halts if, and only if, the

1314: 370:, each member of which is required to meet the following design specifications: 159:

The references used may be made clearer with a different or consistent style of

5655: 5643: 5631: 5619: 2286:

symbols instead of just 2 (0 and 1). For example a trinary Turing machine with

7364:

Lafitte, G.; Papazian, C. (June 2007). "The fabric of small Turing machines".

7343: 6718: 6505: 3585:, because a blank tape has 0 ones), the recursion relations are as follows: a 2563: 6726: 6607: 6564: 6107: 5989: 1578:

states. Starting with an initially blank tape it first creates a sequence of

728:{\displaystyle {\text{num}}(n)\leq \Sigma (n)\leq {\text{space}}(n)\leq S(n)} 7520: 7250: 7032: 6702: 6620: 6041:

The Undecidability of BB(748): Understanding Gödel’s Incompleteness Theorems

5981: 2575: 2508:) offer an entirely new approach to solving pure mathematics problems. Many 2348:

For example, the longest-running 3-state 3-symbol machine found so far runs

1652:— a simple TM, searching for a first 0 on the tape and replacing it with 1. 946: 4755:

The following table lists the exact values and some known lower bounds for

3120:

A 43-state Turing machine has been constructed that halts if, and only if,

1040:

such that no specific number can be proven to have complexity greater than

853:(i.e., which attains the maximum score) is called a busy beaver. For each 17: 7529: 7444:

of busy beaver results which also contains best results and some analysis.

6904: 6233: 6216: 5994: 5965: 1086:, and there are infinitely many true-but-unprovable sentences of the form 7477: 7016: 6341: 6311: 4968:

These are tables of rules for the Turing machines that generate Σ(1) and

4946:

For an example of a 3-state busy beaver's state table and its "run", see

1262:(3) = 21, and determining that Σ(3) = 6 by the procedure just described. 465:-state Turing machine having the largest possible score or running time. 7093: 6652: 5914:"How the Slowest Computer Programs Illuminate Math's Fundamental Limits" 5705: 5693: 5681: 5669: 1024:

consecutive 1s on an initially blank tape. The corresponding variant of

7448: 7282: 6963: 6615: 6525: 6386: 6099: 5729: 3137:> 8 there is at least one digit 2 in the base 3 representation of 2. 1873:

function can be shown to be incomputable by proving, for example, that

461:) game is therefore a contest, depending on definition to find such an 6640: 4179:{\displaystyle S(n)\leq (n+1)\times \Sigma (5n)\times 2^{\Sigma (5n)}} 2322:-symbol machine started on an initially blank tape before halting, and 6371: 6143: 6083: 6012: 7466: 6599: 7193:(2nd ed.). Wien, New York: Springer-Verlag. pp. 237–254. 6932:"The determination of the value of Rado's noncomputable function Σ( 6500: 6481: 6262: 7451:- Reversal Turing Machines, simple and strong subclass of the TMs. 5248: 5143: 3099:

A 745-state binary Turing machine has been constructed that halts

2344:-symbol machine started on an initially blank tape before halting. 824: 335:(745 states), can be expressed in a similar form, where at most a 7434: 7388:

Boolos, George S.; Burgess, John P.; Jeffrey, Richard C. (2007).

7082:

A Lower Bound on Rado's Sigma Function for Binary Turing Machines

2282:

A simple generalization is the extension to Turing machines with

1222:

was used by Lin & Radó to prove that Σ(3) = 6: For a given

827:

isomorphism, hence at most finitely many possible running times.

7476:

for solving the 5-state, 2-symbol busy beaver problem, based on

6641:"A lower bound RADO's sigma function for binary turing machines" 5814:"Amateur Mathematicians Find Fifth 'Busy Beaver' Turing Machine" 412:

The tape alphabet is {0, 1}, with 0 serving as the blank symbol.

7060:

Marxen and Buntrock demonstrate that Σ(5) ≥ 4098 and

6541:"On the Dynamic Qualitative Behaviour of Universal Computation" 409:

The machine uses a single two-way infinite (or unbounded) tape.

6287:"This Turing machine should run forever unless maths is wrong" 6202:

Boolos, Burgess & Jeffrey, 2007. "Computability and Logic"

3103: 3013: 1308: 1274: 136: 81: 40: 6769:"[July 2nd 2024] We have proved "BB(5) = 47,176,870"" 1475:

1s on the tape and then halt. Let us create the composition

1044:, and hence that no specific upper bound can be proven for Σ( 996:> 5, although lower bounds have been established (see the 7415:(Bachelor thesis) (in Slovak). Charles University in Prague. 2922:

states can be designed to enumerate every possible proof in

7136:, August 1984, pages 19–23, also March 1985 p. 23 and 6793: 6082:

Ben-Amram, A. M.; Julstrom, B. A.; Zwick, U. (1996-08-01).

5463:

4098 "1"s with 8191 "0"s interspersed in 47,176,870 steps.

2270:. Likewise we could define an analog to the Σ function for 1238:-state Turing machines can (in principle) be run for up to 980: 741: 3286:

In contrast, the best current (as of 2024) lower bound on

2648:) by some less direct method for it to actually be useful. 1938:-state space champion, and then uses it to write at least 272:

or simply "busy beaver" is a Turing machine that wins the

958:-state 2-symbol Turing machines would be tested until an 815:

It is clear that Σ is a well-defined function: for every

443:

a state to transition into (which may be the Halt state).

5749:"The Busy Beaver Challenge: Story # space-time-diagrams" 3559:(the ultimate output of each machine being its value on 1250:). The approach used by Lin & Radó for the case of 6703:"Improved Bounds for Functions Related to Busy Beavers" 4315:

By defining num(n) to be the maximum number of ones an

2245:

steps. So for the Reversal Turing Machine (RTM) class,

1923:{\displaystyle {\text{space}}(n)<{\text{num}}(3n+3)} 1621:), which contradicts to the definition of the function 242:, one of the first mathematical models of computation. 102: 2374: 4715: 4682: 4649: 4616: 4514: 4441: 4379: 4332: 4243: 4194: 4102: 4002: 3900: 3819: 3787: 3686: 3637: 3594: 3565: 3529: 3509: 3476: 3443: 3371: 3347: 3321: 3292: 3195: 3069: 3042: 3022: 2974: 2948: 2928: 2901: 2881: 2861: 2826: 2793: 2766: 2746: 2657: 2537: 2214: 2194: 2188:

is thereby the largest integer a program with length

2160: 2140: 2120: 2084: 2042: 2022: 1988: 1944: 1879: 1848: 1802: 1771: 1740: 1709: 1519:

writes 1, moves the head right and switches to state

888: 774: 663: 616: 570: 539: 519: 499: 34:. For the online children's educational program, see 6312:"The 8000th Busy Beaver number eludes ZF set theory" 6013:"Life, blogging, and the Busy Beaver function go on" 973:) is an uncomputable function, there are some small 797:{\displaystyle \Sigma :\mathbb {N} \to \mathbb {N} } 657:

These four functions together stand in the relation

7191:

The Universal Turing Machine: A Half-Century Survey

4304:{\displaystyle S(n)\leq (2n-1)\times \Sigma (3n+3)} 3430:{\displaystyle 10^{(10^{(10^{(10^{(\ldots )})})})}} 2716:{\displaystyle 10^{(10^{(10^{(10^{(\ldots )})})})}} 2314:): the largest number of non-zeros printable by an 1765:functions are uncomputable . This can be shown for 1179:= the largest number of shifts made by any halting 473:The rules for one 1-state Turing machine might be: 97:

may be too technical for most readers to understand

7389: 7031:Marxen, Heiner; Buntrock, Jürgen (February 1990). 6007: 6005: 6003: 4948:Turing machine examples § 3-state Busy Beaver 4737: 4697: 4664: 4631: 4598: 4482: 4426: 4364: 4303: 4227: 4178: 4077: 3977: 3884: 3802: 3770: 3671: 3622: 3577: 3551: 3515: 3491: 3462: 3429: 3353: 3333: 3307: 3274: 3082: 3055: 3028: 2996: 2960: 2934: 2914: 2887: 2867: 2847: 2812: 2779: 2752: 2715: 2555: 2220: 2200: 2180: 2146: 2126: 2106: 2070: 2028: 2008: 1961: 1922: 1865: 1834: 1788: 1757: 1726: 992:) has not yet been determined for any instance of 910: 796: 727: 633: 587: 545: 525: 505: 4988:(5), and the best known lower bound for Σ(6) and 3989:The lower bound BB(N) can also be related to the 938:, and hence that Σ is not a computable function. 30:For the 1931 Silly Symphonies animated film, see 7537:The Busy Beaver Competition: a historical survey 7456:The Busy Beaver Problem: A New Millennium Attack 3771:{\displaystyle B_{N}(m)=1+B_{N-2}(1+B_{N}(m-1))} 1835:{\displaystyle \Sigma (n)\leq {\text{space}}(n)} 1585:1s and then doubles it, producing a sequence of 246:taking the longest number of steps to halt. The 6647:. SWCT '64. USA: IEEE Computer Society: 91–94. 6501:"Some unconventional problems in number theory" 4777:is an upper bound for space(5), because S(5) = 7396:(Fifth ed.). Cambridge University Press. 7158:Open Problems in Communication and Computation 6980:Machlin, Rona; Stout, Quentin F. (June 1990). 6738: 6736: 6438:Open Problems in Communication and Computation 6408: 6406: 4078:{\displaystyle A(n,n)>G(4N+3)>A(4,2N+1)} 911:{\displaystyle f:\mathbb {N} \to \mathbb {N} } 378:"operational" states plus a Halt state, where 27:Longest-running Turing machine of a given size 6886:"Computer Studies of Turing Machine Problems" 6701:Ben-Amram, A. M.; Petersen, H. (2002-02-01). 6217:"Computer studies of Turing machine problems" 6144:"BusyBeaver(5) is now known to be 47,176,870" 4365:{\displaystyle {\text{num}}(n)<\Sigma (n)} 3437:, an exponentiated chain of 15 tens equal to 1494:be the number of states of this machine. Let 830:According to the score-based definition, any 8: 7255:"A note on Busy Beavers and other creatures" 6336: 6334: 6332: 6309:Version from May 3rd contained 7918 states: 6084:"A note on busy beavers and other creatures" 5253:Animation of a 4-state, 2-symbol busy beaver 5148:Animation of a 3-state, 2-symbol busy beaver 4427:{\displaystyle S(n)<{\text{num}}(n+o(n))} 3978:{\displaystyle G(N)=1+B_{N-3}(1+B_{N-3}(1))} 1459:denote a Turing machine evaluating function 1285:), under reasonable consistency hypotheses ( 1048:) (the latter is because "the complexity of 390:, with state 1 as the starting state, or by 7530:Busy Beaver Turing Machines - Computerphile 7480:(Georgi Georgiev) nonregular machines list. 6820:Computer studies of Turing machine problems 5699:Evolution of 3-state busy beaver until halt 5687:Evolution of 2-state busy beaver until halt 5355:1 1 1 0 0 (107 steps, thirteen "1"s total) 4089:Relationships between Busy beaver functions 3463:{\displaystyle 10^{10\uparrow \uparrow 14}} 2496:In addition to posing a rather challenging 2336:): the largest number of steps taken by an 1343:. Unsourced material may be challenged and 749:) or even arbitrary programming languages. 284:-state busy beavers by each definition are 75:Learn how and when to remove these messages 4483:{\displaystyle S(n)<{\text{num}}(3n+6)} 1934:-state Turing machine which simulates the 295:Deciding the running time or score of the 7373: 7333: 7272: 7015: 6982:"The complex behavior of simple machines" 6953: 6903: 6480: 6261: 6232: 5612:Evolution of busy beavers with 1-4 states 5476:current 6-state, 2-symbol best contender 4729: 4714: 4681: 4648: 4615: 4563: 4548: 4513: 4457: 4440: 4395: 4378: 4333: 4331: 4242: 4193: 4158: 4101: 4001: 3951: 3926: 3899: 3858: 3839: 3818: 3786: 3744: 3719: 3691: 3685: 3642: 3636: 3599: 3593: 3564: 3534: 3528: 3508: 3499:is probably much larger still than that. 3475: 3448: 3442: 3400: 3392: 3384: 3376: 3370: 3346: 3320: 3291: 3266: 3245: 3230: 3194: 3074: 3068: 3047: 3041: 3021: 2985: 2973: 2947: 2927: 2906: 2900: 2880: 2860: 2825: 2804: 2792: 2771: 2765: 2745: 2686: 2678: 2670: 2662: 2656: 2547: 2542: 2536: 2213: 2193: 2161: 2159: 2139: 2119: 2114:is the length of the shortest program in 2089: 2083: 2047: 2041: 2021: 1989: 1987: 1945: 1943: 1897: 1880: 1878: 1849: 1847: 1818: 1801: 1772: 1770: 1741: 1739: 1710: 1708: 1407:Learn how and when to remove this message 904: 903: 896: 895: 887: 790: 789: 782: 781: 773: 696: 664: 662: 617: 615: 571: 569: 538: 518: 498: 201:Learn how and when to remove this message 183:Learn how and when to remove this message 125:Learn how and when to remove this message 109:, without removing the technical details. 7539:. 70 pages. 2017. <hal-00396880v5> 7156:. In Cover, T. M.; Gopinath, B. (eds.). 6436:. In Cover, T. M.; Gopinath, B. (eds.). 5474: 5359: 5258: 5153: 5076: 5024: 4956: 4789: 4323:it can output), it is possible to show: 3885:{\displaystyle G(N)=B_{N-2}(B_{N-2}(1))} 1071:for which this is true is far less than 212: 7486:"Collatz-like behavior of Busy Beavers" 7226:Sequential Machines and Automata Theory 6167: 6165: 6163: 5853: 5740: 4751:Exact values and lower and upper bounds 1218:The following connection between Σ and 1028:states that, in the context of a given 595:is defined to be the maximum number of 7128:Busy beaver programs are described by 6696: 6694: 6692: 6690: 6688: 6686: 6684: 6682: 6210: 6208: 6137: 5959: 5957: 5955: 5953: 5851: 5849: 5847: 5845: 5843: 5841: 5839: 5837: 5835: 5833: 3334:{\displaystyle 10\uparrow \uparrow 15} 3004:proves its own consistency, violating 2968:. Any theory that proves the value of 2376:Maximal Halting Times and States from 1699:Uncomputability of space(n) and num(n) 382:is a positive integer, and one of the 315:. The concept was first introduced by 6680: 6678: 6676: 6674: 6672: 6670: 6668: 6666: 6664: 6662: 6634: 6632: 6630: 6628: 6215:Lin, Shen; Rado, Tibor (April 1965). 6135: 6133: 6131: 6129: 6127: 6125: 6123: 6121: 6119: 6117: 5951: 5949: 5947: 5945: 5943: 5941: 5939: 5937: 5935: 5933: 3006:Gödel's second incompleteness theorem 2597:-state Turing machine, so if we know 2593:Now, this program is simulated by an 2500:, the busy beaver functions Σ(n) and 765:faster than any computable function. 107:make it understandable to non-experts 7: 7151:"Computing the Busy Beaver Function" 6431:"Computing the Busy Beaver Function" 6077: 6075: 6073: 6071: 6069: 6067: 6065: 6033: 6031: 6029: 5907: 5905: 5903: 5901: 5899: 5897: 5895: 5893: 5807: 5805: 5803: 5776: 5774: 5772: 5770: 5768: 5235:1 1 0 0 (14 steps, six "1"s total). 5012:Result key: (starts at the position 4228:{\displaystyle S(n)\leq \Sigma (9n)} 1667:and so it is also uncomputable. If 1451:) 1s on the tape and then halt. Let 1341:adding citations to reliable sources 1077:Gödel's first incompleteness theorem 429:the symbol in the current tape cell, 339:number of cases need to be checked. 331:(744 states) and the consistency of 7249:Ben-Amram, A. M.; Julstrom, B. A.; 6416:page listing best contenders known. 4641:tends to be close to the square of 1930:: this can be done by designing an 1609:) steps, so the time of working of 1427:) is a computable function and let 366:'s 1962 paper, involves a class of 6868:10.1002/j.1538-7305.1962.tb00480.x 5884:10.1002/j.1538-7305.1962.tb00480.x 4716: 4650: 4530: 4350: 4280: 4210: 4159: 4136: 3477: 3293: 3196: 2636:) was proven by enumerating every 2539: 1803: 997: 941:Moreover, this implies that it is 819:, there are at most finitely many 775: 681: 25: 6955:10.1090/S0025-5718-1983-0689479-6 6936:) for four-state Turing machines" 5912:Pavlus, John (10 December 2020). 5141:1 0 0 (6 steps, four "1"s total) 4674:, and in fact many machines give 3063:, theories with larger values of 2300:generalized busy beaver functions 1962:{\displaystyle {\text{space}}(n)} 1789:{\displaystyle {\text{space}}(n)} 1727:{\displaystyle {\text{space}}(n)} 1695:) must likewise be uncomputable. 1501:denote a Turing machine creating 1004:Complexity and unprovability of Σ 882:Radó's 1962 paper proved that if 823:-state Turing machines as above, 634:{\displaystyle {\text{space}}(n)} 56:This article has multiple issues. 6970:Brady proves that Σ(4) = 13 and 6557:10.25088/ComplexSystems.20.3.265 5704: 5692: 5680: 5668: 5654: 5642: 5630: 5618: 4791:Values of busy beaver functions 4490: (Ben-Amram, et al., 1996) 2476:nondeterministic Turing machines 2371:Nondeterministic Turing machines 1313: 1026:Chaitin's incompleteness theorem 865:-state busy beavers. (Given any 141: 86: 45: 7505:Who can name the bigger number? 7308:Bounds between functions Σ and 7049:from the original on 2006-10-09 6639:Green, Milton W. (1964-11-11). 6038:Riebel, Johannes (March 2023). 2590:if it finds a counterexample.) 2566:: any conjecture that could be 2474:The problem can be extended to 1866:{\displaystyle {\text{num}}(n)} 1758:{\displaystyle {\text{num}}(n)} 1574:. Notice that this machine has 1183:-state 2-symbol Turing machine. 834:-state 2-symbol Turing machine 588:{\displaystyle {\text{num}}(n)} 64:or discuss these issues on the 7568:Metaphors referring to animals 7160:. Springer. pp. 108–112. 6987:Physica D: Nonlinear Phenomena 6930:Brady, Allen H. (April 1983). 6582:Brady, Allen H. (March 1998). 6518:10.1080/0025570X.1979.11976756 6440:. Springer. pp. 108–112. 6142:Aaronson, Scott (2024-07-02). 5964:Aaronson, Scott (2020-09-29). 5361:5-state, 2-symbol busy beaver 5260:4-state, 2-symbol busy beaver 5155:3-state, 2-symbol busy beaver 5078:2-state, 2-symbol busy beaver 5026:1-state, 2-symbol busy beaver 4738:{\displaystyle \Sigma (n)^{2}} 4726: 4719: 4692: 4686: 4659: 4653: 4626: 4620: 4524: 4518: 4477: 4462: 4451: 4445: 4421: 4418: 4412: 4400: 4389: 4383: 4359: 4353: 4344: 4338: 4298: 4283: 4274: 4259: 4253: 4247: 4222: 4213: 4204: 4198: 4171: 4162: 4148: 4139: 4130: 4118: 4112: 4106: 4072: 4051: 4042: 4027: 4018: 4006: 3972: 3969: 3963: 3938: 3910: 3904: 3879: 3876: 3870: 3851: 3829: 3823: 3797: 3791: 3765: 3762: 3750: 3731: 3703: 3697: 3654: 3648: 3611: 3605: 3546: 3540: 3486: 3480: 3452: 3422: 3417: 3412: 3407: 3401: 3393: 3385: 3377: 3348: 3325: 3302: 3296: 3242: 3217: 3205: 3199: 2991: 2978: 2836: 2830: 2708: 2703: 2698: 2693: 2687: 2679: 2671: 2663: 2298:symbols defines the following 2175: 2169: 2101: 2095: 2071:{\displaystyle K_{L}(m)\leq n} 2059: 2053: 2003: 1997: 1956: 1950: 1917: 1902: 1891: 1885: 1860: 1854: 1829: 1823: 1812: 1806: 1783: 1777: 1752: 1746: 1721: 1715: 1130:makes before halting, for any 900: 786: 722: 716: 707: 701: 690: 684: 675: 669: 628: 622: 582: 576: 255:machine will halt eventually. 229:aims at finding a terminating 1: 7484:Ligocki, Shawn (2021-07-17). 7033:"Attacking the Busy Beaver 5" 6855:Bell System Technical Journal 6847:"On non-computable functions" 6743:Ligocki, Shawn (2022-06-21). 6588:The Journal of Symbolic Logic 5871:Bell System Technical Journal 5863:"On non-computable functions" 5661:Rules for 4-state busy beaver 5649:Rules for 3-state busy beaver 5637:Rules for 2-state busy beaver 5625:Rules for 1-state busy beaver 5005:Each machine begins in state 4884:> 10⇈15 (space(n) ≥ Σ(n)) 2380:-case, 2-state, 2-color NDTM 1969:contiguous ones to the tape. 1293:Proof for uncomputability of 934:) for all sufficiently large 7008:10.1016/0167-2789(90)90068-Z 5812:Brubaker, Ben (2024-07-02). 3672:{\displaystyle B_{1}(m)=m+1} 2556:{\displaystyle \Pi _{1}^{0}} 2510:open problems in mathematics 2278:Different numbers of symbols 1012:is defined as follows: The 954:, each of the finitely many 434:and produces three outputs: 223:theoretical computer science 7321:Theory of Computing Systems 7260:Mathematical Systems Theory 6794:"The Busy Beaver Challenge" 6707:Theory of Computing Systems 6621:Free HTML version by author 6088:Mathematical Systems Theory 4311: (Julstrom and Zwick) 2820:, no statement of the form 2813:{\displaystyle n\geq n_{T}} 2520:) for a sufficiently large 1279:Zermelo–Fraenkel set theory 1254:= 3 was to conjecture that 607:states can write on a tape. 426:the current non-Halt state, 7584: 6941:Mathematics of Computation 6177:"Multiway Turing Machines" 5966:"The Busy Beaver Frontier" 5480: 5365: 5264: 5159: 5082: 5072:0 (1 step, one "1" total) 5030: 4945: 4665:{\displaystyle \Sigma (n)} 3623:{\displaystyle B_{N}(0)=1} 3492:{\displaystyle \Sigma (8)} 3308:{\displaystyle \Sigma (6)} 3133:in 1979 is false: for all 3036:is assigned as its number 2492:Open mathematical problems 2016:to be the largest integer 1287:stationary Ramsey property 29: 7344:10.1007/s00224-001-1052-0 7080:Green, Milton W. (1964). 6773:The Busy Beaver Challenge 6719:10.1007/s00224-001-1052-0 6387:"Reversal Turing machine" 3363:Knuth's up-arrow notation 3354:{\displaystyle \uparrow } 3142:Universal Turing machines 1982:. This is done by taking 1632:The uncomputability of Σ( 1613:is strictly greater than 857:, there exist at least 4( 7502:Aaronson, Scott (1999), 7447:Definition of the class 6414:Busy Beaver Competitions 5016:, halts at the position 3993:. It can be shown that: 3552:{\displaystyle B_{N}(m)} 3152:computational complexity 2997:{\displaystyle S(n_{T})} 2895:, a Turing machine with 2107:{\displaystyle K_{L}(m)} 1431:denote a TM, evaluating 1097:Maximum shifts function 1036:, there exists a number 7411:Kropitz, Pavel (2010). 7392:Computability and Logic 5982:10.1145/3427361.3427369 4952:Turing machine examples 4925:≤ 4098 (Σ(n) ≥ num(n)) 2732:Consistency of theories 2181:{\displaystyle {BB}(n)} 2009:{\displaystyle {BB}(n)} 1655:The uncomputability of 1555:denote the composition 1126:= the number of shifts 1106:maximum shifts function 804:, is defined so that Σ( 457:-state busy beaver (BB- 406:as the starting state.) 352:-state busy beaver game 6745:"BB(6, 2) > 10↑↑15" 6539:Zenil, Hector (2012). 6181:www.wolframphysics.org 6049:University of Augsburg 5254: 5149: 4965: 4739: 4699: 4666: 4633: 4600: 4484: 4428: 4366: 4305: 4229: 4180: 4079: 3979: 3886: 3804: 3772: 3673: 3624: 3579: 3553: 3517: 3493: 3464: 3431: 3355: 3335: 3309: 3276: 3084: 3057: 3030: 2998: 2962: 2936: 2916: 2889: 2869: 2849: 2848:{\displaystyle S(n)=k} 2814: 2781: 2754: 2717: 2578:number of cases (e.g. 2557: 2367:steps before halting. 2222: 2208:or less can output in 2202: 2182: 2148: 2128: 2108: 2072: 2030: 2010: 1963: 1924: 1867: 1836: 1790: 1759: 1728: 1523:+ 1, except the state 1112:, defined as follows: 912: 798: 759:noncomputable function 729: 653:-state Turing machine. 635: 589: 547: 527: 507: 218: 7558:Theory of computation 7213:Conway's Game of Life 7112:Dewdney, Alexander K. 7038:Bulletin of the EATCS 6905:10.1145/321264.321270 6825:Ohio State University 6346:Shtetl-Optimized blog 6342:"Three announcements" 6316:Shtetl-Optimized blog 6234:10.1145/321264.321270 6047:(Bachelor's thesis). 5252: 5147: 4960: 4740: 4700: 4667: 4634: 4601: 4485: 4429: 4367: 4306: 4230: 4181: 4080: 3980: 3887: 3805: 3773: 3674: 3625: 3580: 3554: 3518: 3494: 3465: 3432: 3356: 3336: 3310: 3277: 3122:Goldbach's conjecture 3085: 3083:{\displaystyle n_{T}} 3058: 3056:{\displaystyle n_{T}} 3031: 3010:large cardinal axioms 2999: 2963: 2937: 2917: 2915:{\displaystyle n_{T}} 2890: 2870: 2850: 2815: 2782: 2780:{\displaystyle n_{T}} 2755: 2718: 2580:Goldbach's conjecture 2558: 2223: 2203: 2183: 2149: 2129: 2109: 2073: 2031: 2011: 1980:Kolmogorov complexity 1964: 1925: 1868: 1837: 1791: 1760: 1729: 1439:). Given a tape with 1056:" would be proven if 1010:Kolmogorov complexity 913: 799: 730: 636: 590: 548: 528: 508: 325:Goldbach's conjecture 216: 7553:Computability theory 7368:. pp. 219–227. 7103:Ackermann's function 4942:List of busy beavers 4713: 4698:{\displaystyle S(n)} 4680: 4647: 4632:{\displaystyle S(n)} 4614: 4512: 4498:, such that for all 4439: 4377: 4330: 4241: 4192: 4100: 4000: 3898: 3817: 3803:{\displaystyle G(N)} 3785: 3684: 3635: 3592: 3563: 3527: 3507: 3474: 3441: 3369: 3345: 3319: 3290: 3193: 3186:=8 the method gives 3067: 3040: 3020: 2972: 2946: 2926: 2899: 2879: 2859: 2824: 2791: 2764: 2760:, there is a number 2744: 2655: 2535: 2212: 2192: 2158: 2138: 2118: 2082: 2040: 2020: 1986: 1942: 1877: 1846: 1800: 1769: 1738: 1707: 1530:, which halts). Let 1471:1s it will produce 2 1467:. Given a tape with 1337:improve this section 1234:) is known then all 886: 772: 768:The score function, 661: 614: 603:a Turing machine of 568: 537: 517: 497: 343:Technical definition 305:computability theory 7413:Problém Busy Beaver 7228:. New York: Wiley. 7147:Chaitin, Gregory J. 7134:Scientific American 7117:Scientific American 7094:10.1109/SWCT.1964.3 7000:1990PhyD...42...85M 6653:10.1109/SWCT.1964.3 6427:Chaitin, Gregory J. 6272:2016arXiv160504343Y 6175:(4 February 2021). 5781:Weisstein, Eric W. 5477: 5362: 5261: 5156: 5079: 5027: 4976:(2), Σ(3) (but not 4792: 3578:{\displaystyle m=0} 2961:{\displaystyle 0=1} 2725:Goldbach conjecture 2552: 2381: 1443:1s it will produce 1273:) is unprovable in 920:computable function 761:, because it grows 417:transition function 7513:Weisstein, Eric W. 7283:10.1007/BF01192693 7088:. pp. 91–94. 6891:Journal of the ACM 6221:Journal of the ACM 6100:10.1007/BF01192693 5475: 5360: 5259: 5255: 5154: 5150: 5077: 5025: 4966: 4964:head upon halting. 4880:(S(n) ≥ space(n)) 4790: 4735: 4695: 4662: 4629: 4596: 4480: 4424: 4362: 4301: 4225: 4176: 4075: 3991:Ackermann function 3975: 3882: 3800: 3768: 3669: 3620: 3575: 3549: 3513: 3489: 3460: 3453:↑ ↑ 3427: 3365:. This represents 3351: 3331: 3326:↑ ↑ 3305: 3272: 3113:Riemann hypothesis 3080: 3053: 3026: 2994: 2958: 2932: 2912: 2885: 2865: 2845: 2810: 2787:such that for all 2777: 2750: 2713: 2553: 2538: 2375: 2218: 2198: 2178: 2144: 2124: 2104: 2068: 2026: 2006: 1959: 1920: 1863: 1832: 1786: 1755: 1724: 1515:states (the state 908: 794: 725: 631: 585: 543: 523: 503: 402:, ..., with state 337:countably infinite 329:Riemann hypothesis 299:th Busy Beaver is 219: 7442:Historical survey 7403:978-0-521-87752-7 7235:978-0-471-08848-6 7209:cellular automata 7200:978-3-211-82637-9 7167:978-0-387-96621-2 7130:Alexander Dewdney 6817:Shen Lin (1963). 6447:978-0-387-96621-2 6391:skelet.ludost.net 5787:Wolfram MathWorld 5586: 5585: 5468:cellular automata 5456: 5455: 5340: 5339: 5220: 5219: 5128: 5127: 5058: 5057: 4932: 4931: 4576: 4460: 4398: 4336: 3516:{\displaystyle m} 3029:{\displaystyle T} 3016:: if each theory 2935:{\displaystyle T} 2888:{\displaystyle T} 2868:{\displaystyle T} 2855:can be proved in 2753:{\displaystyle T} 2498:mathematical game 2472: 2471: 2272:register machines 2221:{\displaystyle L} 2201:{\displaystyle n} 2147:{\displaystyle m} 2127:{\displaystyle L} 2029:{\displaystyle m} 1948: 1900: 1883: 1852: 1821: 1775: 1744: 1713: 1417: 1416: 1409: 1391: 1191:Radó showed that 878:Non-computability 699: 667: 620: 574: 546:{\displaystyle n} 526:{\displaystyle n} 506:{\displaystyle n} 489:Related functions 419:takes two inputs: 362:), introduced in 313:complexity theory 235:endlessly looping 211: 210: 203: 193: 192: 185: 135: 134: 127: 79: 16:(Redirected from 7575: 7526: 7525: 7499: 7497: 7496: 7440:Pascal Michel's 7416: 7407: 7395: 7379: 7377: 7358:Improved bounds. 7355: 7337: 7305: 7303: 7302: 7293:. Archived from 7276: 7239: 7222:Booth, Taylor L. 7204: 7185: 7183: 7182: 7176: 7170:. Archived from 7155: 7138:April 1985 p. 30 7125: 7097: 7073: 7072: 7069: 7064:(5) ≥ 7057: 7055: 7054: 7021: 7019: 6967: 6957: 6948:(162): 647–665. 6917: 6907: 6871: 6851: 6829: 6828: 6823:(Ph.D. thesis). 6814: 6808: 6807: 6805: 6804: 6790: 6784: 6783: 6781: 6780: 6765: 6759: 6758: 6756: 6755: 6740: 6731: 6730: 6698: 6657: 6656: 6636: 6623: 6619: 6579: 6573: 6568: 6536: 6530: 6529: 6493: 6487: 6486: 6484: 6472: 6466: 6465: 6463: 6462: 6456: 6450:. Archived from 6435: 6423: 6417: 6412:Pascal Michel's 6410: 6401: 6400: 6398: 6397: 6383: 6377: 6376: 6363: 6357: 6356: 6354: 6353: 6338: 6327: 6326: 6324: 6323: 6307: 6301: 6300: 6298: 6297: 6282: 6276: 6275: 6265: 6253: 6247: 6246: 6236: 6212: 6203: 6200: 6194: 6191: 6185: 6184: 6173:Wolfram, Stephen 6169: 6158: 6157: 6155: 6154: 6148:Shtetl-Optimized 6139: 6112: 6111: 6079: 6060: 6059: 6057: 6055: 6046: 6035: 6024: 6023: 6021: 6020: 6009: 5998: 5993: 5961: 5928: 5927: 5925: 5924: 5909: 5888: 5887: 5867: 5855: 5828: 5827: 5825: 5824: 5809: 5798: 5797: 5795: 5793: 5778: 5763: 5762: 5760: 5759: 5745: 5708: 5696: 5684: 5672: 5658: 5646: 5634: 5622: 5596: 5570: 5478: 5417: 5363: 5354: 5351:1 1 1 1 1 1 1 1 5350: 5301: 5262: 5234: 5230: 5204: 5157: 5140: 5139: 5124: 5080: 5071: 5068: 5046: 5028: 5019: 5015: 5001: 4879: 4878: 4875: 4867: 4866: 4838: 4837: 4834: 4793: 4786: 4785: 4782: 4776: 4775: 4772: 4746: 4744: 4742: 4741: 4736: 4734: 4733: 4706: 4704: 4702: 4701: 4696: 4673: 4671: 4669: 4668: 4663: 4640: 4638: 4636: 4635: 4630: 4605: 4603: 4602: 4597: 4592: 4588: 4581: 4577: 4575: 4568: 4567: 4557: 4549: 4504: 4489: 4487: 4486: 4481: 4461: 4458: 4433: 4431: 4430: 4425: 4399: 4396: 4371: 4369: 4368: 4363: 4337: 4334: 4310: 4308: 4307: 4302: 4234: 4232: 4231: 4226: 4185: 4183: 4182: 4177: 4175: 4174: 4084: 4082: 4081: 4076: 3984: 3982: 3981: 3976: 3962: 3961: 3937: 3936: 3891: 3889: 3888: 3883: 3869: 3868: 3850: 3849: 3809: 3807: 3806: 3801: 3777: 3775: 3774: 3769: 3749: 3748: 3730: 3729: 3696: 3695: 3678: 3676: 3675: 3670: 3647: 3646: 3629: 3627: 3626: 3621: 3604: 3603: 3584: 3582: 3581: 3576: 3558: 3556: 3555: 3550: 3539: 3538: 3522: 3520: 3519: 3514: 3498: 3496: 3495: 3490: 3469: 3467: 3466: 3461: 3459: 3458: 3436: 3434: 3433: 3428: 3426: 3425: 3421: 3420: 3416: 3415: 3411: 3410: 3360: 3358: 3357: 3352: 3340: 3338: 3337: 3332: 3314: 3312: 3311: 3306: 3281: 3279: 3278: 3273: 3271: 3270: 3249: 3235: 3234: 3106:is inconsistent. 3094:Notable examples 3089: 3087: 3086: 3081: 3079: 3078: 3062: 3060: 3059: 3054: 3052: 3051: 3035: 3033: 3032: 3027: 3003: 3001: 3000: 2995: 2990: 2989: 2967: 2965: 2964: 2959: 2941: 2939: 2938: 2933: 2921: 2919: 2918: 2913: 2911: 2910: 2894: 2892: 2891: 2886: 2874: 2872: 2871: 2866: 2854: 2852: 2851: 2846: 2819: 2817: 2816: 2811: 2809: 2808: 2786: 2784: 2783: 2778: 2776: 2775: 2759: 2757: 2756: 2751: 2722: 2720: 2719: 2714: 2712: 2711: 2707: 2706: 2702: 2701: 2697: 2696: 2562: 2560: 2559: 2554: 2551: 2546: 2382: 2366: 2365: 2362: 2359: 2356: 2353: 2269: 2261: 2260: 2257: 2244: 2243: 2240: 2234: 2227: 2225: 2224: 2219: 2207: 2205: 2204: 2199: 2187: 2185: 2184: 2179: 2168: 2153: 2151: 2150: 2145: 2133: 2131: 2130: 2125: 2113: 2111: 2110: 2105: 2094: 2093: 2077: 2075: 2074: 2069: 2052: 2051: 2035: 2033: 2032: 2027: 2015: 2013: 2012: 2007: 1996: 1968: 1966: 1965: 1960: 1949: 1946: 1929: 1927: 1926: 1921: 1901: 1898: 1884: 1881: 1872: 1870: 1869: 1864: 1853: 1850: 1841: 1839: 1838: 1833: 1822: 1819: 1795: 1793: 1792: 1787: 1776: 1773: 1764: 1762: 1761: 1756: 1745: 1742: 1733: 1731: 1730: 1725: 1714: 1711: 1412: 1405: 1401: 1398: 1392: 1390: 1349: 1317: 1309: 1178: 1144: 1125: 1092: 1085: 1066: 1052:is greater than 1030:axiomatic system 1000:section below). 983: 917: 915: 914: 909: 907: 899: 852: 803: 801: 800: 795: 793: 785: 753:Score function Σ 744: 734: 732: 731: 726: 700: 697: 668: 665: 647:space complexity 640: 638: 637: 632: 621: 618: 594: 592: 591: 586: 575: 572: 552: 550: 549: 544: 532: 530: 529: 524: 512: 510: 509: 504: 374:The machine has 227:busy beaver game 206: 199: 188: 181: 177: 174: 168: 145: 144: 137: 130: 123: 119: 116: 110: 90: 89: 82: 71: 49: 48: 41: 32:The Busy Beavers 21: 7583: 7582: 7578: 7577: 7576: 7574: 7573: 7572: 7543: 7542: 7535:Pascal Michel. 7511: 7510: 7494: 7492: 7483: 7465:Daniel Briggs' 7430: 7425: 7410: 7404: 7387: 7375:10.1.1.104.3021 7363: 7335:10.1.1.136.5997 7317: 7300: 7298: 7248: 7236: 7220: 7201: 7188: 7180: 7178: 7174: 7168: 7153: 7145: 7110: 7079: 7070: 7067: 7065: 7052: 7050: 7030: 6979: 6929: 6879: 6849: 6841: 6837: 6832: 6816: 6815: 6811: 6802: 6800: 6798:bbchallenge.org 6792: 6791: 6787: 6778: 6776: 6767: 6766: 6762: 6753: 6751: 6742: 6741: 6734: 6700: 6699: 6660: 6638: 6637: 6626: 6600:10.2307/2586607 6581: 6580: 6576: 6572:from publisher. 6545:Complex Systems 6538: 6537: 6533: 6495: 6494: 6490: 6474: 6473: 6469: 6460: 6458: 6454: 6448: 6433: 6425: 6424: 6420: 6411: 6404: 6395: 6393: 6385: 6384: 6380: 6365: 6364: 6360: 6351: 6349: 6340: 6339: 6330: 6321: 6319: 6310: 6308: 6304: 6295: 6293: 6284: 6283: 6279: 6255: 6254: 6250: 6214: 6213: 6206: 6201: 6197: 6192: 6188: 6171: 6170: 6161: 6152: 6150: 6141: 6140: 6115: 6081: 6080: 6063: 6053: 6051: 6044: 6037: 6036: 6027: 6018: 6016: 6011: 6010: 6001: 5963: 5962: 5931: 5922: 5920: 5918:Quanta Magazine 5911: 5910: 5891: 5865: 5857: 5856: 5831: 5822: 5820: 5818:Quanta Magazine 5811: 5810: 5801: 5791: 5789: 5780: 5779: 5766: 5757: 5755: 5753:bbchallenge.org 5747: 5746: 5742: 5738: 5721: 5716: 5715: 5714: 5713: 5712: 5709: 5701: 5700: 5697: 5689: 5688: 5685: 5677: 5676: 5673: 5664: 5663: 5662: 5659: 5651: 5650: 5647: 5639: 5638: 5635: 5627: 5626: 5623: 5614: 5613: 5603: 5594: 5566: 5413: 5352: 5348: 5297: 5232: 5228: 5200: 5137: 5136: 5120: 5069: 5066: 5042: 5017: 5013: 4997: 4980:(3)), Σ(4) and 4962: 4955: 4944: 4876: 4873: 4871: 4864: 4862: 4835: 4832: 4830: 4783: 4780: 4778: 4773: 4770: 4768: 4753: 4725: 4711: 4710: 4708: 4678: 4677: 4675: 4645: 4644: 4642: 4612: 4611: 4609: 4559: 4558: 4550: 4544: 4537: 4533: 4510: 4509: 4499: 4437: 4436: 4375: 4374: 4328: 4327: 4239: 4238: 4190: 4189: 4154: 4098: 4097: 4091: 3998: 3997: 3947: 3922: 3896: 3895: 3854: 3835: 3815: 3814: 3783: 3782: 3740: 3715: 3687: 3682: 3681: 3638: 3633: 3632: 3595: 3590: 3589: 3561: 3560: 3530: 3525: 3524: 3505: 3504: 3472: 3471: 3470:. The value of 3444: 3439: 3438: 3396: 3388: 3380: 3372: 3367: 3366: 3343: 3342: 3317: 3316: 3288: 3287: 3262: 3226: 3191: 3190: 3171: 3166: 3161: 3148:Turing machines 3144: 3096: 3070: 3065: 3064: 3043: 3038: 3037: 3018: 3017: 2981: 2970: 2969: 2944: 2943: 2924: 2923: 2902: 2897: 2896: 2877: 2876: 2857: 2856: 2822: 2821: 2800: 2789: 2788: 2767: 2762: 2761: 2742: 2741: 2734: 2682: 2674: 2666: 2658: 2653: 2652: 2533: 2532: 2494: 2489: 2373: 2363: 2360: 2357: 2354: 2351: 2349: 2280: 2267: 2265: 2258: 2255: 2253: 2251: 2241: 2238: 2236: 2232: 2210: 2209: 2190: 2189: 2156: 2155: 2136: 2135: 2116: 2115: 2085: 2080: 2079: 2043: 2038: 2037: 2018: 2017: 1984: 1983: 1975: 1973:Generalizations 1940: 1939: 1875: 1874: 1844: 1843: 1798: 1797: 1767: 1766: 1736: 1735: 1705: 1704: 1701: 1665:halting problem 1584: 1560: 1547: 1540: 1534:denote the sum 1529: 1514: 1507: 1499: 1493: 1413: 1402: 1396: 1393: 1350: 1348: 1334: 1318: 1307: 1283:axiom of choice 1176: 1148: 1143: 1131: 1116: 1102: 1087: 1080: 1057: 1034:natural numbers 1006: 979: 884: 883: 880: 839: 770: 769: 755: 740: 737:lambda calculus 659: 658: 612: 611: 566: 565: 535: 534: 515: 514: 495: 494: 491: 471: 368:Turing machines 345: 309:halting problem 240:Turing machines 207: 196: 195: 194: 189: 178: 172: 169: 158: 152:has an unclear 146: 142: 131: 120: 114: 111: 103:help improve it 100: 91: 87: 50: 46: 39: 28: 23: 22: 15: 12: 11: 5: 7581: 7579: 7571: 7570: 7565: 7563:Large integers 7560: 7555: 7545: 7544: 7541: 7540: 7533: 7527: 7508: 7500: 7481: 7463: 7452: 7445: 7438: 7429: 7428:External links 7426: 7424: 7423: 7422: 7421: 7408: 7402: 7385: 7384: 7383: 7361: 7360: 7359: 7315: 7314: 7313: 7274:10.1.1.75.1297 7267:(4): 375–386. 7246: 7245: 7244: 7234: 7218: 7217: 7216: 7199: 7186: 7166: 7143: 7142: 7141: 7108: 7107: 7106: 7077: 7076: 7075: 7028: 7027: 7026: 6994:(1–3): 85–98. 6977: 6976: 6975: 6927: 6926: 6925: 6898:(2): 196–212. 6884:(April 1965). 6877: 6876: 6875: 6862:(3): 877–884. 6838: 6836: 6833: 6831: 6830: 6809: 6785: 6760: 6732: 6658: 6624: 6594:(1): 331–332. 6574: 6551:(3): 265–277. 6531: 6488: 6467: 6446: 6418: 6402: 6378: 6358: 6328: 6302: 6277: 6248: 6227:(2): 196–212. 6204: 6195: 6193:Chaitin (1987) 6186: 6159: 6113: 6094:(4): 375–386. 6061: 6025: 5999: 5929: 5889: 5878:(3): 877–884. 5829: 5799: 5764: 5739: 5737: 5734: 5733: 5732: 5727: 5720: 5717: 5710: 5703: 5702: 5698: 5691: 5690: 5686: 5679: 5678: 5674: 5667: 5666: 5665: 5660: 5653: 5652: 5648: 5641: 5640: 5636: 5629: 5628: 5624: 5617: 5616: 5615: 5611: 5610: 5609: 5608: 5602: 5601:Visualizations 5599: 5588: 5587: 5584: 5583: 5577: 5571: 5563: 5557: 5551: 5545: 5541: 5540: 5534: 5528: 5522: 5516: 5510: 5504: 5500: 5499: 5496: 5493: 5490: 5487: 5484: 5481: 5458: 5457: 5454: 5453: 5447: 5441: 5435: 5429: 5423: 5419: 5418: 5410: 5404: 5398: 5392: 5386: 5382: 5381: 5378: 5375: 5372: 5369: 5366: 5342: 5341: 5338: 5337: 5331: 5325: 5319: 5313: 5309: 5308: 5302: 5294: 5288: 5282: 5278: 5277: 5274: 5271: 5268: 5265: 5222: 5221: 5218: 5217: 5211: 5205: 5197: 5193: 5192: 5186: 5180: 5174: 5170: 5169: 5166: 5163: 5160: 5130: 5129: 5126: 5125: 5117: 5111: 5107: 5106: 5100: 5094: 5090: 5089: 5086: 5083: 5060: 5059: 5056: 5055: 5052: 5048: 5047: 5039: 5035: 5034: 5031: 4984:(4), Σ(5) and 4972:(1), Σ(2) and 4943: 4940: 4930: 4929: 4926: 4923: 4920: 4917: 4914: 4908: 4907: 4906:> 10⇈15 () 4904: 4901: 4898: 4895: 4892: 4886: 4885: 4882: 4859: 4856: 4853: 4850: 4844: 4843: 4842:> 10⇈15 () 4840: 4828: 4825: 4822: 4819: 4813: 4812: 4809: 4806: 4803: 4800: 4797: 4752: 4749: 4732: 4728: 4724: 4721: 4718: 4694: 4691: 4688: 4685: 4661: 4658: 4655: 4652: 4628: 4625: 4622: 4619: 4607: 4606: 4595: 4591: 4587: 4584: 4580: 4574: 4571: 4566: 4562: 4556: 4553: 4547: 4543: 4540: 4536: 4532: 4529: 4526: 4523: 4520: 4517: 4492: 4491: 4479: 4476: 4473: 4470: 4467: 4464: 4456: 4453: 4450: 4447: 4444: 4434: 4423: 4420: 4417: 4414: 4411: 4408: 4405: 4402: 4394: 4391: 4388: 4385: 4382: 4372: 4361: 4358: 4355: 4352: 4349: 4346: 4343: 4340: 4313: 4312: 4300: 4297: 4294: 4291: 4288: 4285: 4282: 4279: 4276: 4273: 4270: 4267: 4264: 4261: 4258: 4255: 4252: 4249: 4246: 4236: 4224: 4221: 4218: 4215: 4212: 4209: 4206: 4203: 4200: 4197: 4187: 4173: 4170: 4167: 4164: 4161: 4157: 4153: 4150: 4147: 4144: 4141: 4138: 4135: 4132: 4129: 4126: 4123: 4120: 4117: 4114: 4111: 4108: 4105: 4090: 4087: 4086: 4085: 4074: 4071: 4068: 4065: 4062: 4059: 4056: 4053: 4050: 4047: 4044: 4041: 4038: 4035: 4032: 4029: 4026: 4023: 4020: 4017: 4014: 4011: 4008: 4005: 3987: 3986: 3974: 3971: 3968: 3965: 3960: 3957: 3954: 3950: 3946: 3943: 3940: 3935: 3932: 3929: 3925: 3921: 3918: 3915: 3912: 3909: 3906: 3903: 3893: 3881: 3878: 3875: 3872: 3867: 3864: 3861: 3857: 3853: 3848: 3845: 3842: 3838: 3834: 3831: 3828: 3825: 3822: 3799: 3796: 3793: 3790: 3779: 3778: 3767: 3764: 3761: 3758: 3755: 3752: 3747: 3743: 3739: 3736: 3733: 3728: 3725: 3722: 3718: 3714: 3711: 3708: 3705: 3702: 3699: 3694: 3690: 3679: 3668: 3665: 3662: 3659: 3656: 3653: 3650: 3645: 3641: 3630: 3619: 3616: 3613: 3610: 3607: 3602: 3598: 3574: 3571: 3568: 3548: 3545: 3542: 3537: 3533: 3512: 3488: 3485: 3482: 3479: 3457: 3454: 3451: 3447: 3424: 3419: 3414: 3409: 3406: 3403: 3399: 3395: 3391: 3387: 3383: 3379: 3375: 3350: 3330: 3327: 3324: 3304: 3301: 3298: 3295: 3284: 3283: 3269: 3265: 3261: 3258: 3255: 3252: 3248: 3244: 3241: 3238: 3233: 3229: 3225: 3222: 3219: 3216: 3213: 3210: 3207: 3204: 3201: 3198: 3170: 3169:Green machines 3167: 3165: 3162: 3160: 3157: 3143: 3140: 3139: 3138: 3126: 3125: 3117: 3116: 3108: 3107: 3101:if and only if 3095: 3092: 3077: 3073: 3050: 3046: 3025: 2993: 2988: 2984: 2980: 2977: 2957: 2954: 2951: 2931: 2909: 2905: 2884: 2864: 2844: 2841: 2838: 2835: 2832: 2829: 2807: 2803: 2799: 2796: 2774: 2770: 2749: 2733: 2730: 2729: 2728: 2710: 2705: 2700: 2695: 2692: 2689: 2685: 2681: 2677: 2673: 2669: 2665: 2661: 2649: 2572:counterexample 2550: 2545: 2541: 2493: 2490: 2488: 2485: 2470: 2469: 2466: 2463: 2459: 2458: 2455: 2452: 2448: 2447: 2444: 2441: 2437: 2436: 2433: 2430: 2426: 2425: 2422: 2419: 2415: 2414: 2411: 2408: 2404: 2403: 2400: 2397: 2393: 2392: 2389: 2386: 2372: 2369: 2346: 2345: 2323: 2279: 2276: 2263: 2249: 2217: 2197: 2177: 2174: 2171: 2167: 2164: 2143: 2123: 2103: 2100: 2097: 2092: 2088: 2067: 2064: 2061: 2058: 2055: 2050: 2046: 2025: 2005: 2002: 1999: 1995: 1992: 1974: 1971: 1958: 1955: 1952: 1919: 1916: 1913: 1910: 1907: 1904: 1896: 1893: 1890: 1887: 1862: 1859: 1856: 1831: 1828: 1825: 1817: 1814: 1811: 1808: 1805: 1785: 1782: 1779: 1754: 1751: 1748: 1723: 1720: 1717: 1700: 1697: 1582: 1558: 1545: 1538: 1527: 1512: 1505: 1497: 1491: 1415: 1414: 1321: 1319: 1312: 1306: 1291: 1185: 1184: 1172: 1146: 1139: 1101: 1095: 1088:Σ(10⇈10) < 1005: 1002: 969:Even though Σ( 906: 902: 898: 894: 891: 879: 876: 792: 788: 784: 780: 777: 763:asymptotically 754: 751: 724: 721: 718: 715: 712: 709: 706: 703: 695: 692: 689: 686: 683: 680: 677: 674: 671: 655: 654: 630: 627: 624: 608: 584: 581: 578: 542: 522: 502: 490: 487: 482: 481: 478: 470: 467: 447: 446: 445: 444: 441: 438: 432: 431: 430: 427: 421: 420: 415:The machine's 413: 410: 407: 344: 341: 292:respectively. 263:th busy beaver 209: 208: 191: 190: 154:citation style 149: 147: 140: 133: 132: 94: 92: 85: 80: 54: 53: 51: 44: 26: 24: 14: 13: 10: 9: 6: 4: 3: 2: 7580: 7569: 7566: 7564: 7561: 7559: 7556: 7554: 7551: 7550: 7548: 7538: 7534: 7531: 7528: 7523: 7522: 7517: 7516:"Busy Beaver" 7514: 7509: 7507: 7506: 7501: 7491: 7487: 7482: 7479: 7475: 7471: 7468: 7464: 7461: 7457: 7453: 7450: 7446: 7443: 7439: 7436: 7435:Heiner Marxen 7432: 7431: 7427: 7418: 7417: 7414: 7409: 7405: 7399: 7394: 7393: 7386: 7381: 7380: 7376: 7371: 7367: 7362: 7357: 7356: 7353: 7349: 7345: 7341: 7336: 7331: 7327: 7323: 7322: 7316: 7311: 7307: 7306: 7297:on 2018-07-21 7296: 7292: 7288: 7284: 7280: 7275: 7270: 7266: 7262: 7261: 7256: 7252: 7247: 7241: 7240: 7237: 7231: 7227: 7223: 7219: 7214: 7210: 7206: 7205: 7202: 7196: 7192: 7187: 7177:on 2017-12-30 7173: 7169: 7163: 7159: 7152: 7148: 7144: 7139: 7135: 7131: 7127: 7126: 7123: 7119: 7118: 7113: 7109: 7104: 7099: 7098: 7095: 7091: 7087: 7083: 7078: 7063: 7059: 7058: 7048: 7044: 7040: 7039: 7034: 7029: 7023: 7022: 7018: 7017:2027.42/28528 7013: 7009: 7005: 7001: 6997: 6993: 6989: 6988: 6983: 6978: 6973: 6969: 6968: 6965: 6961: 6956: 6951: 6947: 6943: 6942: 6937: 6935: 6928: 6923: 6919: 6918: 6915: 6911: 6906: 6901: 6897: 6893: 6892: 6887: 6883: 6878: 6873: 6872: 6869: 6865: 6861: 6857: 6856: 6848: 6844: 6840: 6839: 6834: 6826: 6822: 6821: 6813: 6810: 6799: 6795: 6789: 6786: 6774: 6770: 6764: 6761: 6750: 6746: 6739: 6737: 6733: 6728: 6724: 6720: 6716: 6712: 6708: 6704: 6697: 6695: 6693: 6691: 6689: 6687: 6685: 6683: 6681: 6679: 6677: 6675: 6673: 6671: 6669: 6667: 6665: 6663: 6659: 6654: 6650: 6646: 6642: 6635: 6633: 6631: 6629: 6625: 6622: 6617: 6613: 6609: 6605: 6601: 6597: 6593: 6589: 6585: 6578: 6575: 6571: 6570:PDF available 6566: 6562: 6558: 6554: 6550: 6546: 6542: 6535: 6532: 6527: 6523: 6519: 6515: 6511: 6508: 6507: 6502: 6498: 6492: 6489: 6483: 6478: 6471: 6468: 6457:on 2017-12-30 6453: 6449: 6443: 6439: 6432: 6428: 6422: 6419: 6415: 6409: 6407: 6403: 6392: 6388: 6382: 6379: 6375:. 2019-02-13. 6374: 6373: 6368: 6362: 6359: 6347: 6343: 6337: 6335: 6333: 6329: 6317: 6313: 6306: 6303: 6292: 6288: 6285:Aron, Jacob. 6281: 6278: 6273: 6269: 6264: 6259: 6252: 6249: 6244: 6240: 6235: 6230: 6226: 6222: 6218: 6211: 6209: 6205: 6199: 6196: 6190: 6187: 6182: 6178: 6174: 6168: 6166: 6164: 6160: 6149: 6145: 6138: 6136: 6134: 6132: 6130: 6128: 6126: 6124: 6122: 6120: 6118: 6114: 6109: 6105: 6101: 6097: 6093: 6089: 6085: 6078: 6076: 6074: 6072: 6070: 6068: 6066: 6062: 6050: 6043: 6042: 6034: 6032: 6030: 6026: 6014: 6008: 6006: 6004: 6000: 5996: 5995:PDF available 5991: 5987: 5983: 5979: 5975: 5971: 5967: 5960: 5958: 5956: 5954: 5952: 5950: 5948: 5946: 5944: 5942: 5940: 5938: 5936: 5934: 5930: 5919: 5915: 5908: 5906: 5904: 5902: 5900: 5898: 5896: 5894: 5890: 5885: 5881: 5877: 5873: 5872: 5864: 5860: 5854: 5852: 5850: 5848: 5846: 5844: 5842: 5840: 5838: 5836: 5834: 5830: 5819: 5815: 5808: 5806: 5804: 5800: 5788: 5784: 5783:"Busy Beaver" 5777: 5775: 5773: 5771: 5769: 5765: 5754: 5750: 5744: 5741: 5735: 5731: 5728: 5726: 5725:Rayo's number 5723: 5722: 5718: 5707: 5695: 5683: 5671: 5657: 5645: 5633: 5621: 5607: 5600: 5598: 5592: 5582: 5578: 5576: 5572: 5569: 5564: 5562: 5558: 5556: 5552: 5550: 5546: 5543: 5542: 5539: 5535: 5533: 5529: 5527: 5523: 5521: 5517: 5515: 5511: 5509: 5505: 5502: 5501: 5497: 5494: 5491: 5488: 5485: 5482: 5479: 5473: 5472: 5471: 5469: 5464: 5462: 5452: 5448: 5446: 5442: 5440: 5436: 5434: 5430: 5428: 5424: 5421: 5420: 5416: 5411: 5409: 5405: 5403: 5399: 5397: 5393: 5391: 5387: 5384: 5383: 5379: 5376: 5373: 5370: 5367: 5364: 5358: 5357: 5356: 5346: 5336: 5332: 5330: 5326: 5324: 5320: 5318: 5314: 5311: 5310: 5307: 5303: 5300: 5295: 5293: 5289: 5287: 5283: 5280: 5279: 5275: 5272: 5269: 5266: 5263: 5257: 5256: 5251: 5247: 5245: 5241: 5236: 5226: 5216: 5212: 5210: 5206: 5203: 5198: 5195: 5194: 5191: 5187: 5185: 5181: 5179: 5175: 5172: 5171: 5167: 5164: 5161: 5158: 5152: 5151: 5146: 5142: 5134: 5123: 5118: 5116: 5112: 5109: 5108: 5105: 5101: 5099: 5095: 5092: 5091: 5087: 5084: 5081: 5075: 5074: 5073: 5064: 5053: 5050: 5049: 5045: 5040: 5037: 5036: 5032: 5029: 5023: 5022: 5021: 5010: 5008: 5003: 5000: 4993: 4991: 4987: 4983: 4979: 4975: 4971: 4959: 4953: 4949: 4941: 4939: 4937: 4927: 4924: 4921: 4918: 4915: 4913: 4910: 4909: 4905: 4902: 4899: 4896: 4893: 4891: 4888: 4887: 4883: 4881: 4860: 4857: 4854: 4851: 4849: 4846: 4845: 4841: 4829: 4826: 4823: 4820: 4818: 4815: 4814: 4810: 4807: 4804: 4801: 4798: 4795: 4794: 4788: 4766: 4762: 4758: 4750: 4748: 4730: 4722: 4689: 4683: 4656: 4623: 4617: 4593: 4589: 4585: 4582: 4578: 4572: 4569: 4564: 4560: 4554: 4551: 4545: 4541: 4538: 4534: 4527: 4521: 4515: 4508: 4507: 4506: 4502: 4497: 4474: 4471: 4468: 4465: 4454: 4448: 4442: 4435: 4415: 4409: 4406: 4403: 4392: 4386: 4380: 4373: 4356: 4347: 4341: 4326: 4325: 4324: 4322: 4318: 4295: 4292: 4289: 4286: 4277: 4271: 4268: 4265: 4262: 4256: 4250: 4244: 4237: 4235: (Buro) 4219: 4216: 4207: 4201: 4195: 4188: 4186: (Rado) 4168: 4165: 4155: 4151: 4145: 4142: 4133: 4127: 4124: 4121: 4115: 4109: 4103: 4096: 4095: 4094: 4088: 4069: 4066: 4063: 4060: 4057: 4054: 4048: 4045: 4039: 4036: 4033: 4030: 4024: 4021: 4015: 4012: 4009: 4003: 3996: 3995: 3994: 3992: 3966: 3958: 3955: 3952: 3948: 3944: 3941: 3933: 3930: 3927: 3923: 3919: 3916: 3913: 3907: 3901: 3894: 3873: 3865: 3862: 3859: 3855: 3846: 3843: 3840: 3836: 3832: 3826: 3820: 3813: 3812: 3811: 3794: 3788: 3759: 3756: 3753: 3745: 3741: 3737: 3734: 3726: 3723: 3720: 3716: 3712: 3709: 3706: 3700: 3692: 3688: 3680: 3666: 3663: 3660: 3657: 3651: 3643: 3639: 3631: 3617: 3614: 3608: 3600: 3596: 3588: 3587: 3586: 3572: 3569: 3566: 3543: 3535: 3531: 3510: 3500: 3483: 3455: 3449: 3445: 3404: 3397: 3389: 3381: 3373: 3364: 3341:, where each 3328: 3322: 3299: 3267: 3263: 3259: 3256: 3253: 3250: 3246: 3239: 3236: 3231: 3227: 3223: 3220: 3214: 3211: 3208: 3202: 3189: 3188: 3187: 3185: 3181: 3177: 3168: 3163: 3159:Known results 3158: 3156: 3153: 3149: 3141: 3136: 3132: 3128: 3127: 3123: 3119: 3118: 3114: 3110: 3109: 3105: 3102: 3098: 3097: 3093: 3091: 3075: 3071: 3048: 3044: 3023: 3015: 3011: 3007: 2986: 2982: 2975: 2955: 2952: 2949: 2929: 2907: 2903: 2882: 2862: 2842: 2839: 2833: 2827: 2805: 2801: 2797: 2794: 2772: 2768: 2747: 2739: 2731: 2726: 2690: 2683: 2675: 2667: 2659: 2650: 2647: 2643: 2639: 2635: 2631: 2627: 2626: 2625: 2622: 2620: 2616: 2612: 2608: 2604: 2600: 2596: 2591: 2589: 2585: 2581: 2577: 2573: 2569: 2565: 2548: 2543: 2531:Consider any 2529: 2527: 2523: 2519: 2515: 2511: 2507: 2503: 2499: 2491: 2486: 2484: 2482: 2477: 2467: 2464: 2461: 2460: 2456: 2453: 2450: 2449: 2445: 2442: 2439: 2438: 2434: 2431: 2428: 2427: 2423: 2420: 2417: 2416: 2412: 2409: 2406: 2405: 2401: 2398: 2395: 2394: 2390: 2387: 2384: 2383: 2379: 2370: 2368: 2343: 2339: 2335: 2331: 2327: 2324: 2321: 2317: 2313: 2309: 2305: 2304: 2303: 2301: 2297: 2293: 2289: 2285: 2277: 2275: 2273: 2248: 2229: 2215: 2195: 2172: 2165: 2162: 2141: 2134:that outputs 2121: 2098: 2090: 2086: 2065: 2062: 2056: 2048: 2044: 2023: 2000: 1993: 1990: 1981: 1972: 1970: 1953: 1937: 1933: 1914: 1911: 1908: 1905: 1894: 1888: 1857: 1826: 1815: 1809: 1780: 1749: 1718: 1698: 1696: 1694: 1690: 1686: 1682: 1678: 1674: 1670: 1666: 1662: 1658: 1653: 1651: 1647: 1643: 1639: 1635: 1630: 1628: 1624: 1620: 1616: 1612: 1608: 1604: 1600: 1596: 1593:will produce 1592: 1588: 1581: 1577: 1573: 1569: 1565: 1561: 1554: 1549: 1544: 1537: 1533: 1526: 1522: 1518: 1511: 1504: 1500: 1490: 1486: 1482: 1478: 1474: 1470: 1466: 1462: 1458: 1454: 1450: 1446: 1442: 1438: 1434: 1430: 1426: 1422: 1419:Suppose that 1411: 1408: 1400: 1389: 1386: 1382: 1379: 1375: 1372: 1368: 1365: 1361: 1358: – 1357: 1356:"Busy beaver" 1353: 1352:Find sources: 1346: 1342: 1338: 1332: 1331: 1327: 1322:This section 1320: 1316: 1311: 1310: 1304: 1300: 1296: 1292: 1290: 1288: 1284: 1280: 1276: 1272: 1268: 1263: 1261: 1257: 1253: 1249: 1245: 1241: 1237: 1233: 1229: 1225: 1221: 1216: 1214: 1210: 1206: 1202: 1198: 1194: 1189: 1182: 1175: 1171: 1167: 1163: 1159: 1155: 1151: 1147: 1142: 1138: 1134: 1129: 1123: 1119: 1115: 1114: 1113: 1111: 1107: 1100: 1096: 1094: 1091: 1084: 1078: 1074: 1070: 1064: 1060: 1055: 1051: 1047: 1043: 1039: 1035: 1031: 1027: 1023: 1019: 1015: 1011: 1008:A variant of 1003: 1001: 999: 995: 991: 987: 982: 976: 972: 967: 965: 961: 957: 953: 948: 945:by a general 944: 939: 937: 933: 929: 925: 921: 892: 889: 877: 875: 872: 868: 864: 860: 856: 850: 846: 842: 837: 833: 828: 826: 822: 818: 813: 811: 807: 778: 766: 764: 760: 752: 750: 748: 743: 738: 719: 713: 710: 704: 693: 687: 678: 672: 652: 648: 644: 625: 610:The function 609: 606: 602: 598: 579: 564:The function 563: 562: 561: 558: 556: 555:noncomputable 540: 520: 500: 488: 486: 479: 476: 475: 474: 468: 466: 464: 460: 456: 452: 442: 439: 436: 435: 433: 428: 425: 424: 423: 422: 418: 414: 411: 408: 405: 401: 397: 393: 389: 385: 381: 377: 373: 372: 371: 369: 365: 361: 359: 353: 351: 342: 340: 338: 334: 333:ZF set theory 330: 326: 322: 318: 314: 310: 306: 302: 298: 293: 291: 287: 283: 279: 275: 271: 270: 264: 262: 256: 253: 249: 243: 241: 236: 232: 228: 224: 215: 205: 202: 187: 184: 176: 166: 162: 156: 155: 150:This article 148: 139: 138: 129: 126: 118: 108: 104: 98: 95:This article 93: 84: 83: 78: 76: 69: 68: 63: 62: 57: 52: 43: 42: 37: 33: 19: 7519: 7503: 7493:. Retrieved 7489: 7433:The page of 7412: 7391: 7365: 7325: 7319: 7309: 7299:. Retrieved 7295:the original 7264: 7258: 7225: 7190: 7179:. Retrieved 7172:the original 7157: 7133: 7121: 7115: 7081: 7061: 7051:. Retrieved 7042: 7036: 6991: 6985: 6971: 6945: 6939: 6933: 6921: 6895: 6889: 6859: 6853: 6845:(May 1962). 6819: 6812: 6801:. Retrieved 6797: 6788: 6777:. Retrieved 6775:. 2024-07-02 6772: 6763: 6752:. Retrieved 6748: 6710: 6706: 6644: 6591: 6587: 6577: 6548: 6544: 6534: 6512:(2): 67–70. 6509: 6504: 6491: 6470: 6459:. Retrieved 6452:the original 6437: 6421: 6394:. Retrieved 6390: 6381: 6370: 6361: 6350:. Retrieved 6348:. 2016-05-03 6345: 6320:. Retrieved 6318:. 2016-05-03 6315: 6305: 6294:. Retrieved 6291:NewScientist 6290: 6280: 6251: 6224: 6220: 6198: 6189: 6180: 6151:. Retrieved 6147: 6091: 6087: 6054:24 September 6052:. Retrieved 6040: 6017:. Retrieved 6015:. 2023-07-05 5997:from author. 5976:(3): 32–54. 5973: 5969: 5921:. Retrieved 5917: 5875: 5869: 5861:(May 1962). 5821:. Retrieved 5817: 5790:. Retrieved 5786: 5756:. Retrieved 5752: 5743: 5604: 5590: 5589: 5580: 5574: 5567: 5560: 5554: 5548: 5537: 5531: 5525: 5519: 5513: 5507: 5465: 5460: 5459: 5450: 5444: 5438: 5432: 5426: 5414: 5407: 5401: 5395: 5389: 5344: 5343: 5334: 5328: 5322: 5316: 5305: 5298: 5291: 5285: 5243: 5239: 5237: 5224: 5223: 5214: 5208: 5201: 5189: 5183: 5177: 5132: 5131: 5121: 5114: 5103: 5097: 5062: 5061: 5043: 5011: 5006: 5004: 4998: 4994: 4989: 4985: 4981: 4977: 4973: 4969: 4967: 4933: 4911: 4889: 4869: 4847: 4816: 4764: 4760: 4756: 4754: 4608: 4500: 4495: 4493: 4321:unary number 4316: 4314: 4092: 3988: 3780: 3501: 3285: 3183: 3179: 3175: 3172: 3164:Lower bounds 3145: 3134: 2735: 2645: 2641: 2637: 2633: 2629: 2623: 2618: 2614: 2610: 2606: 2602: 2598: 2594: 2592: 2587: 2583: 2530: 2525: 2521: 2517: 2513: 2505: 2501: 2495: 2487:Applications 2480: 2473: 2377: 2347: 2341: 2337: 2333: 2329: 2325: 2319: 2315: 2311: 2307: 2299: 2295: 2291: 2287: 2283: 2281: 2246: 2230: 1976: 1935: 1931: 1702: 1692: 1688: 1684: 1680: 1676: 1672: 1668: 1660: 1656: 1654: 1649: 1645: 1641: 1637: 1633: 1631: 1626: 1622: 1618: 1614: 1610: 1606: 1602: 1598: 1594: 1590: 1586: 1579: 1575: 1571: 1567: 1563: 1556: 1552: 1550: 1542: 1535: 1531: 1524: 1520: 1516: 1509: 1502: 1495: 1488: 1484: 1480: 1476: 1472: 1468: 1464: 1460: 1456: 1452: 1448: 1444: 1440: 1436: 1432: 1428: 1424: 1420: 1418: 1403: 1394: 1384: 1377: 1370: 1363: 1351: 1335:Please help 1323: 1302: 1298: 1294: 1270: 1269:for which S( 1266: 1264: 1259: 1255: 1251: 1247: 1243: 1239: 1235: 1231: 1227: 1223: 1219: 1217: 1212: 1208: 1204: 1200: 1196: 1192: 1190: 1186: 1180: 1173: 1169: 1165: 1161: 1157: 1153: 1149: 1140: 1136: 1132: 1127: 1121: 1117: 1109: 1105: 1103: 1098: 1089: 1082: 1068: 1062: 1058: 1053: 1049: 1045: 1041: 1037: 1021: 1017: 1016:of a number 1013: 1007: 998:Known values 993: 989: 974: 970: 968: 963: 959: 955: 951: 940: 935: 931: 927: 923: 881: 870: 866: 862: 861:− 1)! 858: 854: 848: 844: 840: 835: 831: 829: 820: 816: 814: 809: 805: 767: 756: 656: 650: 642: 604: 601:unary number 596: 559: 492: 483: 472: 462: 458: 454: 450: 448: 416: 403: 399: 395: 391: 387: 383: 379: 375: 357: 355: 349: 348: 346: 320: 301:incomputable 296: 294: 289: 285: 281: 277: 273: 268: 266: 260: 259: 257: 251: 247: 244: 226: 220: 197: 179: 170: 151: 121: 115:October 2016 112: 96: 72: 65: 59: 58:Please help 55: 36:Busy Beavers 7124:(2): 10–17. 7045:: 247–251. 6882:Radó, Tibor 6880:Lin, Shen; 6843:Radó, Tibor 6713:(1): 1–11. 6497:Erdõs, Paul 5970:SIGACT News 5859:Radó, Tibor 5792:21 November 5246:(3) = 21.) 5054:(not used) 3523:ones to be 2294:states and 1679:states for 1081:Σ(10⇈10) = 943:undecidable 18:Busy Beaver 7547:Categories 7495:2022-07-12 7301:2022-07-07 7181:2022-07-07 7053:2020-01-19 6835:References 6803:2024-07-02 6779:2024-07-02 6754:2024-07-04 6506:Math. Mag. 6482:2107.12475 6461:2022-07-07 6396:2022-02-10 6352:2018-04-27 6322:2016-09-25 6296:2016-09-25 6263:1605.04343 6153:2024-07-04 6019:2023-08-27 5923:2020-12-11 5823:2024-07-03 5758:2024-07-09 5018:underlined 4707:less than 3985:for even N 3131:Paul Erdős 2564:conjecture 2036:such that 1367:newspapers 1014:complexity 838:for which 739:(sequence 597:contiguous 364:Tibor Radó 317:Tibor Radó 165:footnoting 61:improve it 7532:, Youtube 7521:MathWorld 7370:CiteSeerX 7330:CiteSeerX 7269:CiteSeerX 7251:Zwick, U. 6727:1433-0490 6608:0022-4812 6565:0891-2513 6108:1433-0490 5990:0163-5700 5014:overlined 4796:Function 4717:Σ 4651:Σ 4570:⁡ 4531:Σ 4528:≤ 4351:Σ 4281:Σ 4278:× 4269:− 4257:≤ 4211:Σ 4208:≤ 4160:Σ 4152:× 4137:Σ 4134:× 4116:≤ 3956:− 3931:− 3892:for odd N 3863:− 3844:− 3757:− 3724:− 3478:Σ 3405:… 3349:↑ 3294:Σ 3260:× 3254:≈ 3237:− 3224:× 3215:× 3209:≥ 3197:Σ 3115:is false. 2798:≥ 2691:… 2576:countable 2568:disproven 2540:Π 2235:1s after 2063:≤ 1816:≤ 1804:Σ 1650:Increment 1589:1s. Then 1397:July 2024 1324:does not 1281:with the 947:algorithm 922:, then Σ( 901:→ 787:→ 776:Σ 711:≤ 694:≤ 682:Σ 679:≤ 173:July 2024 67:talk page 7490:sligocki 7460:archived 7352:10429773 7328:: 1–11. 7291:30937913 7253:(1996). 7224:(1967). 7149:(1987). 7047:Archived 6914:17789208 6749:sligocki 6499:(1979). 6429:(1987). 6243:17789208 5719:See also 5135:0 0 1 1 4903:4098 () 4848:space(n) 4811:6-state 4808:5-state 4805:4-state 4802:3-state 4799:2-state 4579:⌉ 4546:⌈ 2574:among a 2528:states. 2340:-state, 2318:-state, 2078:, where 1557:Create_n 1496:Create_n 1487:and let 1301:) and Σ( 1156:) = max{ 1032:for the 161:citation 7470:archive 7467:website 6996:Bibcode 6964:2007539 6616:2586607 6526:2689842 6268:Bibcode 5730:Turmite 5591:Result: 5461:Result: 5345:Result: 5225:Result: 5133:Result: 5063:Result: 4827:107 () 4745:⁠ 4709:⁠ 4705:⁠ 4676:⁠ 4672:⁠ 4643:⁠ 4639:⁠ 4610:⁠ 3182:. When 2391:states 1842:. The 1381:scholar 1345:removed 1330:sources 1061:> Σ( 984:in the 981:A028444 926:) > 918:is any 745:in the 742:A333479 469:Example 231:program 101:Please 7478:Skelet 7400: 7372: 7350: 7332: 7289: 7271: 7232: 7197: 7164: 6962: 6912: 6725: 6614: 6606: 6563: 6524: 6444: 6372:GitHub 6241: 6106: 5988: 5347:0 0 1 5227:0 0 1 4950:, and 4922:12 () 4912:num(n) 4900:13 () 4858:16 () 4824:21 () 2738:theory 2570:via a 2388:steps 2266:(6) ≥ 2252:(6) ≥ 1932:(3n+3) 1564:Double 1477:Double 1457:Double 1383: 1376: 1369: 1362: 1354: 1207:) ≥ Σ( 847:) = Σ( 649:of an 453:. The 311:, and 307:, the 225:, the 7474:forum 7348:S2CID 7287:S2CID 7175:(PDF) 7154:(PDF) 6960:JSTOR 6910:S2CID 6850:(PDF) 6612:JSTOR 6522:JSTOR 6477:arXiv 6455:(PDF) 6434:(PDF) 6258:arXiv 6239:S2CID 6045:(PDF) 5866:(PDF) 5736:Notes 4992:(6). 4919:6 () 4916:4 () 4897:6 () 4894:4 () 4855:7 () 4852:4 () 4821:6 () 4763:), Σ( 3257:8.248 2262:and Σ 1947:space 1882:space 1820:space 1774:space 1712:space 1703:Both 1648:with 1646:Clean 1642:EvalΣ 1640:with 1638:EvalS 1572:Clean 1568:EvalS 1485:Clean 1481:EvalS 1453:Clean 1429:EvalS 1388:JSTOR 1374:books 1226:, if 1073:10⇈10 988:). Σ( 825:up to 698:space 619:space 451:score 7472:and 7398:ISBN 7230:ISBN 7211:and 7195:ISBN 7162:ISBN 7025:(Ω). 6723:ISSN 6604:ISSN 6561:ISSN 6442:ISBN 6104:ISSN 6056:2024 5986:ISSN 5794:2023 5065:0 0 4890:Σ(n) 4817:S(n) 4455:< 4393:< 4348:< 4046:> 4022:> 2588:only 2268:6147 2233:6147 1895:< 1734:and 1644:and 1611:BadS 1591:BadS 1553:BadS 1551:Let 1360:news 1328:any 1326:cite 1164:) | 986:OEIS 966:).) 747:OEIS 643:read 360:game 354:(or 347:The 290:S(n) 288:and 286:Σ(n) 163:and 7458:" ( 7449:RTM 7420:TM. 7340:doi 7279:doi 7132:in 7122:251 7090:doi 7071:870 7068:176 7012:hdl 7004:doi 6950:doi 6900:doi 6864:doi 6715:doi 6649:doi 6596:doi 6553:doi 6514:doi 6229:doi 6096:doi 5978:doi 5880:doi 5470:. 5242:. ( 4936:Coq 4877:870 4874:176 4868:() 4865:289 4839:() 4836:870 4833:176 4784:870 4781:176 4774:870 4771:176 4561:log 4503:≥ 2 4459:num 4397:num 4335:num 3361:is 3315:is 3104:ZFC 3014:ZFC 3012:in 2468:18 2457:18 2446:15 2435:11 2364:540 2361:342 2358:170 2355:334 2352:112 2350:119 2264:RTM 2259:970 2256:339 2250:RTM 2242:970 2239:339 1899:num 1851:num 1743:num 1629:). 1339:by 1275:ZFC 1093:.) 871:all 666:num 573:num 356:BB- 267:BB- 258:An 221:In 105:to 7549:: 7518:. 7488:. 7346:. 7338:. 7326:35 7324:. 7285:. 7277:. 7265:29 7263:. 7257:. 7120:. 7084:. 7066:47 7043:40 7041:. 7035:. 7010:. 7002:. 6992:42 6990:. 6984:. 6958:. 6946:40 6944:. 6938:. 6908:. 6896:12 6894:. 6888:. 6860:41 6858:. 6852:. 6796:. 6771:. 6747:. 6735:^ 6721:. 6711:35 6709:. 6705:. 6661:^ 6643:. 6627:^ 6610:. 6602:. 6592:63 6590:. 6586:. 6559:. 6549:20 6547:. 6543:. 6520:. 6510:52 6503:. 6405:^ 6389:. 6369:. 6344:. 6331:^ 6314:. 6289:. 6266:. 6237:. 6225:12 6223:. 6219:. 6207:^ 6179:. 6162:^ 6146:. 6116:^ 6102:. 6092:29 6090:. 6086:. 6064:^ 6028:^ 6002:^ 5984:. 5974:51 5972:. 5968:. 5932:^ 5916:. 5892:^ 5876:41 5874:. 5868:. 5832:^ 5816:. 5802:^ 5785:. 5767:^ 5751:. 5593:1 5579:0R 5573:0R 5565:1R 5559:1L 5553:0R 5547:0L 5544:1 5536:0R 5530:1L 5524:0L 5518:1L 5512:1R 5506:1R 5503:0 5498:F 5495:E 5492:D 5489:C 5486:B 5483:A 5449:0L 5443:1L 5437:0L 5431:1R 5425:1L 5422:1 5412:1R 5406:1L 5400:1R 5394:1R 5388:1R 5385:0 5380:E 5377:D 5374:C 5371:B 5368:A 5333:0R 5327:1L 5321:0L 5315:1L 5312:1 5304:1R 5296:1R 5290:1L 5284:1R 5281:0 5276:D 5273:C 5270:B 5267:A 5231:1 5213:1L 5207:1R 5199:1R 5196:1 5188:1L 5182:0R 5176:1R 5173:0 5168:C 5165:B 5162:A 5119:1R 5113:1L 5110:1 5102:1L 5096:1R 5093:0 5088:B 5085:A 5051:1 5041:1R 5038:0 5033:A 5020:) 5002:. 4938:. 4928:? 4872:47 4870:≤ 4863:12 4861:≥ 4831:47 4779:47 4769:47 4747:. 4505:: 3810:: 3456:14 3450:10 3446:10 3398:10 3390:10 3382:10 3374:10 3329:15 3323:10 3268:44 3264:10 3232:92 2684:10 2676:10 2668:10 2660:10 2462:7 2451:6 2440:5 2429:4 2424:7 2418:3 2413:4 2407:2 2402:2 2396:1 2385:p 2332:, 2310:, 2306:Σ( 2302:: 2254:47 2237:47 2228:. 2154:: 1570:| 1566:| 1562:| 1548:. 1541:+ 1483:| 1479:| 1463:+ 1199:, 1168:∈ 1135:∈ 1108:, 398:, 394:, 265:, 248:n- 70:. 7524:. 7498:. 7454:" 7406:. 7378:. 7354:. 7342:: 7312:. 7310:S 7304:. 7281:: 7238:. 7203:. 7184:. 7140:. 7105:. 7096:. 7092:: 7062:S 7056:. 7020:. 7014:: 7006:: 6998:: 6972:S 6966:. 6952:: 6934:k 6922:S 6916:. 6902:: 6870:. 6866:: 6827:. 6806:. 6782:. 6757:. 6729:. 6717:: 6655:. 6651:: 6618:. 6598:: 6567:. 6555:: 6528:. 6516:: 6485:. 6479:: 6464:. 6399:. 6355:. 6325:. 6299:. 6274:. 6270:: 6260:: 6245:. 6231:: 6183:. 6156:. 6110:. 6098:: 6058:. 6022:. 5992:. 5980:: 5926:. 5886:. 5882:: 5826:. 5796:. 5761:. 5595:0 5581:E 5575:B 5568:H 5561:A 5555:F 5549:D 5538:C 5532:F 5526:E 5520:C 5514:C 5508:B 5451:A 5445:D 5439:E 5433:B 5427:C 5415:H 5408:A 5402:D 5396:C 5390:B 5353:1 5349:0 5335:A 5329:D 5323:C 5317:B 5306:D 5299:H 5292:A 5286:B 5244:S 5240:S 5233:1 5229:1 5215:A 5209:B 5202:H 5190:C 5184:C 5178:B 5138:1 5122:H 5115:B 5104:A 5098:B 5070:0 5067:1 5044:H 5007:A 4999:H 4990:S 4986:S 4982:S 4978:S 4974:S 4970:S 4954:. 4765:n 4761:n 4759:( 4757:S 4731:2 4727:) 4723:n 4720:( 4693:) 4690:n 4687:( 4684:S 4660:) 4657:n 4654:( 4627:) 4624:n 4621:( 4618:S 4594:. 4590:) 4586:c 4583:+ 4573:n 4565:2 4555:n 4552:8 4542:+ 4539:n 4535:( 4525:) 4522:n 4519:( 4516:S 4501:n 4496:c 4478:) 4475:6 4472:+ 4469:n 4466:3 4463:( 4452:) 4449:n 4446:( 4443:S 4422:) 4419:) 4416:n 4413:( 4410:o 4407:+ 4404:n 4401:( 4390:) 4387:n 4384:( 4381:S 4360:) 4357:n 4354:( 4345:) 4342:n 4339:( 4317:n 4299:) 4296:3 4293:+ 4290:n 4287:3 4284:( 4275:) 4272:1 4266:n 4263:2 4260:( 4254:) 4251:n 4248:( 4245:S 4223:) 4220:n 4217:9 4214:( 4205:) 4202:n 4199:( 4196:S 4172:) 4169:n 4166:5 4163:( 4156:2 4149:) 4146:n 4143:5 4140:( 4131:) 4128:1 4125:+ 4122:n 4119:( 4113:) 4110:n 4107:( 4104:S 4073:) 4070:1 4067:+ 4064:N 4061:2 4058:, 4055:4 4052:( 4049:A 4043:) 4040:3 4037:+ 4034:N 4031:4 4028:( 4025:G 4019:) 4016:n 4013:, 4010:n 4007:( 4004:A 3973:) 3970:) 3967:1 3964:( 3959:3 3953:N 3949:B 3945:+ 3942:1 3939:( 3934:3 3928:N 3924:B 3920:+ 3917:1 3914:= 3911:) 3908:N 3905:( 3902:G 3880:) 3877:) 3874:1 3871:( 3866:2 3860:N 3856:B 3852:( 3847:2 3841:N 3837:B 3833:= 3830:) 3827:N 3824:( 3821:G 3798:) 3795:N 3792:( 3789:G 3766:) 3763:) 3760:1 3754:m 3751:( 3746:N 3742:B 3738:+ 3735:1 3732:( 3727:2 3721:N 3717:B 3713:+ 3710:1 3707:= 3704:) 3701:m 3698:( 3693:N 3689:B 3667:1 3664:+ 3661:m 3658:= 3655:) 3652:m 3649:( 3644:1 3640:B 3618:1 3615:= 3612:) 3609:0 3606:( 3601:N 3597:B 3573:0 3570:= 3567:m 3547:) 3544:m 3541:( 3536:N 3532:B 3511:m 3487:) 3484:8 3481:( 3423:) 3418:) 3413:) 3408:) 3402:( 3394:( 3386:( 3378:( 3303:) 3300:6 3297:( 3282:. 3251:2 3247:/ 3243:) 3240:1 3228:3 3221:7 3218:( 3212:3 3206:) 3203:8 3200:( 3184:n 3180:n 3176:n 3135:n 3076:T 3072:n 3049:T 3045:n 3024:T 2992:) 2987:T 2983:n 2979:( 2976:S 2956:1 2953:= 2950:0 2930:T 2908:T 2904:n 2883:T 2863:T 2843:k 2840:= 2837:) 2834:n 2831:( 2828:S 2806:T 2802:n 2795:n 2773:T 2769:n 2748:T 2709:) 2704:) 2699:) 2694:) 2688:( 2680:( 2672:( 2664:( 2646:n 2644:( 2642:S 2638:n 2634:n 2632:( 2630:S 2619:n 2617:( 2615:S 2611:n 2609:( 2607:S 2603:n 2601:( 2599:S 2595:n 2584:n 2549:0 2544:1 2526:n 2522:n 2518:n 2516:( 2514:S 2506:n 2504:( 2502:S 2481:p 2465:6 2454:7 2443:8 2432:7 2421:6 2410:4 2399:2 2378:p 2342:m 2338:n 2334:m 2330:n 2328:( 2326:S 2320:m 2316:n 2312:m 2308:n 2296:m 2292:n 2288:m 2284:m 2247:S 2216:L 2196:n 2176:) 2173:n 2170:( 2166:B 2163:B 2142:m 2122:L 2102:) 2099:m 2096:( 2091:L 2087:K 2066:n 2060:) 2057:m 2054:( 2049:L 2045:K 2024:m 2004:) 2001:n 1998:( 1994:B 1991:B 1957:) 1954:n 1951:( 1936:n 1918:) 1915:3 1912:+ 1909:n 1906:3 1903:( 1892:) 1889:n 1886:( 1861:) 1858:n 1855:( 1830:) 1827:n 1824:( 1813:) 1810:n 1807:( 1784:) 1781:n 1778:( 1753:) 1750:n 1747:( 1722:) 1719:n 1716:( 1693:n 1691:( 1689:S 1685:n 1683:( 1681:S 1677:n 1673:n 1671:( 1669:S 1661:n 1659:( 1657:S 1634:n 1627:n 1625:( 1623:S 1619:N 1617:( 1615:S 1607:N 1605:( 1603:S 1599:N 1597:( 1595:S 1587:N 1583:0 1580:n 1576:N 1559:0 1546:0 1543:n 1539:0 1536:n 1532:N 1528:0 1525:n 1521:i 1517:i 1513:0 1510:n 1506:0 1503:n 1498:0 1492:0 1489:n 1473:n 1469:n 1465:n 1461:n 1449:n 1447:( 1445:S 1441:n 1437:n 1435:( 1433:S 1425:n 1423:( 1421:S 1410:) 1404:( 1399:) 1395:( 1385:· 1378:· 1371:· 1364:· 1347:. 1333:. 1305:) 1303:n 1299:n 1297:( 1295:S 1271:n 1267:n 1260:S 1256:S 1252:n 1248:n 1244:n 1242:( 1240:S 1236:n 1232:n 1230:( 1228:S 1224:n 1220:S 1213:S 1209:n 1205:n 1203:( 1201:S 1197:n 1193:S 1181:n 1177:} 1174:n 1170:E 1166:M 1162:M 1160:( 1158:s 1154:n 1152:( 1150:S 1145:, 1141:n 1137:E 1133:M 1128:M 1124:) 1122:M 1120:( 1118:s 1110:S 1099:S 1090:n 1083:n 1069:k 1065:) 1063:k 1059:n 1054:k 1050:n 1046:k 1042:k 1038:k 1022:n 1018:n 994:n 990:n 975:n 971:n 964:n 960:n 956:n 952:n 936:n 932:n 930:( 928:f 924:n 905:N 897:N 893:: 890:f 867:n 863:n 859:n 855:n 851:) 849:n 845:M 843:( 841:σ 836:M 832:n 821:n 817:n 810:n 806:n 791:N 783:N 779:: 723:) 720:n 717:( 714:S 708:) 705:n 702:( 691:) 688:n 685:( 676:) 673:n 670:( 651:n 629:) 626:n 623:( 605:n 583:) 580:n 577:( 541:n 521:n 501:n 463:n 459:n 455:n 404:A 400:C 396:B 392:A 388:n 384:n 380:n 376:n 358:n 350:n 321:n 297:n 282:n 278:n 274:n 269:n 261:n 252:n 204:) 198:( 186:) 180:( 175:) 171:( 167:. 157:. 128:) 122:( 117:) 113:( 99:. 77:) 73:( 38:. 20:)

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Index