Talk:Busy beaver

Wrong machine for "best contender"?

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)

busy beaver hierarchy conjectures

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)

Example and description do not match

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)

Countably infinite?

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

Noncomputability

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

Contradiction wrt Ackermann function

In the subsubsection on "Green machines", it says Green's lower bound ⁠$G(N)$⁠ can also be related to the Ackermann function. In particular, $$A(N,N)<G(4N+3)<A(4,2N+1)$$ for all positive integers ⁠$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)

Value of num(5)

According to the articles below (all from the Busy Beaver Community wiki), num(5) is known to be 165.

https://wiki.bbchallenge.org/wiki/0RB1LD_1LC1RB_1LD1RE_1LA1LE_1LZ0RC

https://wiki.bbchallenge.org/wiki/Maximum_Consecutive_Ones_Function

https://wiki.bbchallenge.org/wiki/TYBR:_2025

I do not know how to make edits on Wikipedia or cite articles correctly, so I'm hoping a more knowledgeable editor can add this information which is currently missing in the corresponding table under the "Known results" section. ~2026-35330-18 (talk) 01:31, 16 June 2026 (UTC)

As an additional comment, it seems this value was not mentioned in the BB(5) paper (or any other value regarding the num function). ~2026-35330-18 (talk) 01:34, 16 June 2026 (UTC)

Σ(n) and S(n) used before their introduction

Both Σ(n) and S(n) are casually used without any explanation in the intro; only much later are they introduced and explained. ~2026-35692-52 (talk) 16:49, 23 June 2026 (UTC)

The same applies to $space(n)$ and $num(n)$. - Jochen Burghardt (talk) 17:13, 23 June 2026 (UTC)