Talk:Busy beaver

I've been using Google's Gemini 2.5 Pro Experimental large language model to create summaries for the most popular articles with {{Technical}} templates. This article, Busy beaver, has such a template above the entire article. Here is the paragraph summary at grade 5 reading level which Gemini 2.5 Pro suggested:

The busy beaver game is like a puzzle for simple computer programs. The goal is to find a program of a certain size that uses a long tape with 0s and 1s. You want the program that runs for the longest time before it stops, or the one that writes the most 1s on the tape before stopping. Programs that would run forever are not allowed. The program that wins for its size is called a "busy beaver." It's very hard to find these winning programs, especially for bigger sizes, and it's impossible to know the best score or longest time for all possible sizes.

While I have read and may have made some modifications to that summary, I am not going to add it to the article because I want other editors to review, revise if appropriate, and add it instead. This is an experiment with a few dozen articles initially to see how these suggestions are received, and after a week or two, I will decide how to proceed. Thank you for your consideration. Cramulator (talk) 13:10, 2 April 2025 (UTC)

Use of LLM needs to be discussed by the entire Wikipedia community, not just those interested in one article. You can start at WP:Village pump. Sundayclose (talk) 16:03, 2 April 2025 (UTC)

I am retracting this and the other LLM-generated suggestions due to clear negative consensus at the Village Pump. I will be posting a thorough postmortem report in mid-April to the source code release page. Thanks to all who commented on the suggestions both negatively and positively, and especially to those editors who have manually addressed the overly technical cleanup issue on six, so far, of the 68 articles where suggestions were posted. Cramulator (talk) 01:48, 5 April 2025 (UTC)

The article currently says: "Radó's 1962 paper proved that if ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ is any computable function, then Σ(n) > f(n) for all sufficiently large n, and hence that Σ is not a computable function."

Here's why Σ(n) > f(n) does nothing to prove that Σ is not a computable function:

Let ${\displaystyle g:\mathbb {N} \to \mathbb {N} }$ be defined as g(n) = f(n) + 1. Because f(n) + 1 > f(n), g(n) > f(n) for all n, and therefore, g is supposedly not a computable function, because we accepted that one function being greater than another for all n is proof of its non-computability.

I presume that Radó's paper does not contain such a ridiculous statement, but the article does contain it.

By any computable function there it means for every computable function, not just a particular computable function like f(n)=1 and g is a particular function not one that varies with the choice of f. What it is saying is if you choose any computable function f then there is a value of n for which Σ(n) > f(n) for all sufficiently large n, and that definitely is enough to establish that it is not a computable function as if it was computable one could choose f = Σ an you'd get a contradiction as for sufficiently large n it would be bigger than itself. NadVolum (talk) 09:28, 18 April 2025 (UTC)

I think, Σ(n) became computable, thanks to Agustín Rayo.

Rayo(n) is defined as: "the smallest natural number greater than all natural numbers named by an expression in the language of first-order set theory with n symbols or less". This means, the smallest number, that requires at least n + 1 symbols in the first-order set theory.

So, the first-order set theory, Rayo(n), is a strong symbol function, that is a lot stronger than Σ(n).

Rayo's number is Rayo(10¹⁰⁰) and in How big is Rayo's Number 拉約數, Carbrickscity said, that Rayo(10¹⁰⁰) is uncomputable, because 10¹⁰⁰ symbols are way too many to write out.

conjectures:

1. Because it can be determined, that Rayo(7339) > S(2⁶⁵⁵³⁶ - 1), where S(n) is the maximum shifts function, meaning that the first-order set theory would need only 7340 symbols, to express Σ(2⁶⁵⁵³⁶ - 1), Σ(n) became computable, thanks to Agustín Rayo, so Σ(n) should be the very last entry in List of googolisms/Higher computable level.

2. If X is the largest number of symbols, that can be fully written out within the practical limits (The largest I found with these conditions is 2*10¹⁵ (The longest mathematical proof ever) and because 10⁶¹ (Planck times since the big bang) and 10⁸⁰ (particles in the observable universe) are the theoretical limits, X can be either 2*10¹⁵ itself or between 2*10¹⁵ and 10⁶¹.), then the upper limit for higher computable level is Rayo(X - 1).

3. Agustín Rayo's original goal (which got aborted by the big number duel) was, to find out the exact value of TREE(3), where he thought, if he could write out the symbols for TREE(3), he might be able to find out the exact value of TREE(3), so he created his strong symbol function, Rayo(n), because the 2↑↑1000 symbols in the strictly finite mathematics would be way too many to write out. 2A00:6020:A123:8B00:8C1A:BB1D:AB4A:6BDE (talk) 12:26, 14 May 2025 (UTC)

I also see the "nonsense" in this part of the theorem in Radó's paper.

Theorem. Σ(n) >− f(n) for every computable (that is, general recursive) function f(n). Hence Σ(n) is not computable.

The proof in the paper only covers the first sentence of the theorem.

The second sentence is stated without proof and can only be inferred from the first for a finite set of computable functions. For all elements of an infinite set there could always exist a larger element which is also in the set. This is why Radó writes in the abstract that:

this paper is based on the principle that a finite, non-empty set of non-negative integers has a largest element.

again in the introduction that:

we shall use only the principle that a non-empty finite set of non-negative integers has a largest element.

and again in the summary that:

Inspection of the preceding presentation shows that we used in our constructions only the following "principle of the largest element": If E is a non-empty, finite set of non-negative integers, then E has a largest element.

@Mr swordfish reverted my attempt to resolve this issue in the article by clarifying this assumption of the paper. I hope someone restores my solution to this issue or proposes a better solution. Nativeblue (talk) 23:32, 21 June 2025 (UTC)

I removed the phrase "...assuming that the set of all computable functions is finite" because the paper does not and would not make that assumption. The set of all computable functions is countable, but it is not finite. Mr. Swordfish (talk) 00:08, 22 June 2025 (UTC)

In the "List of busy beavers" section is what the text claims is the "current 6-state, 2-symbol best contender", which takes "more than 10↑↑15 steps". I think that's the S(n) of a previous best contender. As I understand it, the current best 6-state, 2-symbol machine has a lower limit of 2↑↑↑5 steps (and 2↑↑↑5 score), as shown in the "Exact values and lower and upper bounds" section just above. Shouldn't a different machine (and different lower-bound number of steps) be shown here? DKMell (talk) 18:46, 22 August 2025 (UTC)

g_α(n): slow-growing hierarchy

H_α(n): Hardy hierarchy

f_α(n): fast-growing hierarchy

B_α(n): busy beaver hierarchy

R_α(n): Rayo hierarchy

BC(n): Busy beaver ordinal catching function, that counts the points, where g_α(n), H_α(n), f_α(n) and B_α(n) are equivalent.

RC(n): Rayo ordinal catching function, that counts the points, where g_α(n), H_α(n), f_α(n), B_α(n) and R_α(n) are equivalent.

conjectures

1. If Σ(n) = B₁(n) = f_ω1^CK(n), Elga's function = B_ω1^CK(n) and B_ω^ω+163(n) = g_X(n) for some large X, then Ξ(n) is B_X(n).

2. Rayo's number, which is Rayo(10¹⁰⁰) or R₁(10¹⁰⁰), is the first catching point, where g_x(n), H_x(n), f_x(n) and B_x(n) are equivalent, represented as BC(1) in the busy beaver ordinal catching function.

3. The Rayo hierarchy starts with R_m(n) = BC(m), up to R_ω(n) = BC(ω), but then, R_ω+1(n) becomes BC(Ω). F7(n), which is R_ζ0(n) in the Rayo hierarchy, is BC(BC₁(2)) in the other 4 hierarchies.

4. Little Bigeddon and Sasquatch are Γ₀ and ψ(Ω_ω) in the Rayo hierarchy, and BC(Ω₂) and BC(Ω_ω) in the other 4 hierarchies.

5. Oblivion is BC(BC₁(2)) in the Rayo hierarchy and if BC(BC₁(2)) = ψ(Z) for some large Z, then Oblivion is BC(Z) in the other 4 hierarchies.

6. Utter Oblivion is the first catching point, where g_z(n), H_z(n), f_z(n), B_z(n) and R_z(n) are equivalent, represented as RC(1) in the Rayo ordinal catching function, and is also the smallest number, where ψ(z) and BC(z) are equivalent. 2003:E8:5F03:7F00:4CA7:5A2C:6BEA:A114 (talk) 16:19, 1 November 2025 (UTC)

What do you want to say? Should this text be added to the article? - Jochen Burghardt (talk) 20:00, 1 November 2025 (UTC)

The example given and description here: https://en.wikipedia.org/wiki/Busy_beaver#Example do not match. The example has a machine that halts at a score of 2, the description says it goes on forever and is ineligible. ~2025-31538-24 (talk) 22:46, 5 November 2025 (UTC)

...can be expressed in a similar form, where at most a countably infinite number of cases need to be checked.

This is the last sentence in the lead. What does this mean? It is, of course, not obvious that it suffice to check a countable number of states to prove certain things, but isn't the point of the paragraph that it takes finite number checks? The cited article doesn't seem to include the term "countably."

My guess is that the citation is regarding the 744 state machine for the Riemann hypothesis, in which case it is misplaced. — xo Ergur (talk) 09:23, 2 January 2026 (UTC)

Countably is correct. So for instance it is straightforward to check Goldbach's conjecture for any particular number, If it is checked for all numbers then its truth or falsity is determined - but that would take a countably infinite time. Since the infinite test can be encoded as a small Turing machine so it stops if the conjecture is false then if that machine is smaller than the busy beaver for 25 states it suffices to just run the test that long. NadVolum (talk) 16:49, 31 January 2026 (UTC)

...if it were possible to compute the functions Σ(n) and S(n) for all n...

As far as I am aware, "noncomputable" does not mean "cannot be computed."

A pedantic note: you don't need to actually "compute" them (very hard); you only need upper bounds (possibly not quite as hard, in theory).

This could be addressed with a rewrite of the sentence in question. — xo Ergur (talk) 09:36, 2 January 2026 (UTC)

There cannot exists a computable function that gives an upper bound for these because that would enable one to calculate the busy beaver function, and also exact values for all these functions in a finite time. NadVolum (talk) 16:35, 31 January 2026 (UTC)

But you can compute them . — xo Ergur (talk) 14:19, 19 February 2026 (UTC)

No, you can't. The OEIS page says so, too. This is the reason why only the first five members can be given there. - Jochen Burghardt (talk) 14:39, 19 February 2026 (UTC)

No, the reason only the first five are given is because there have only been five computed. As far as I can see, noncomputable means there is no single Turing machine that computes them. That wouldn't mean they can't be computed. — xo Ergur (talk) 08:10, 20 February 2026 (UTC)

There is no single Turing machine that computes all of them. Computing some of them is possible (and has been done for the first 5 members). - Jochen Burghardt (talk) 09:09, 20 February 2026 (UTC)

In the subsubsection on "Green machines", it says Green's lower bound ⁠${\displaystyle G(N)}$⁠ can also be related to the Ackermann function. In particular, $${\displaystyle A(N,N)<G(4N+3)<A(4,2N+1)}$$ for all positive integers ⁠${\displaystyle N}$⁠. This implies that A(N,N) < A(4, 2N+1) for all N. This is absurd. JRSpriggs (talk) 03:25, 31 January 2026 (UTC)

The Ackermann function as used in the paper is defined with the arguments swapped, so we should swap them back for this article. IndigoManedWolf (talk) 04:49, 31 January 2026 (UTC)

To IndigoManedWolf: Thank you for fixing this. JRSpriggs (talk) 14:31, 31 January 2026 (UTC)