Talk:Champions

Self-Reporting and Verification

This champions page has ended up with a lot of self reported and (I assume) not independently verified champions. I'm conflicted about this: On the one hand I want this wiki to have an encyclopedic/Wikipedia style: it would include things which are known, established and verified. On the other hand, I don't want to stifle innovation or gatekeep what counts as proper verification. As a compromise I have updated the table to add a "Verification" column. The idea here is to indicate which results have been independently verified by another contributor. My idea is that that verification should include some sort of write-up (wiki page, blog post, etc) describing the TM and how it is known to run this long. I have linked to examples of my own for Pavel's BB(6) and Daniel's BB(16) champions. I would love to see some independent analyses of other TMs here (especially smaller ones like Racheline's BB(14) > Graham champion). Sligocki (talk) 16:19, 10 December 2024 (UTC)

Particularly interesting is Racheline's BB(14) > Graham champion. --Konkhra (talk) 01:53, 12 December 2024 (UTC)

Larger champions

What are the known two-symbol champions beyond BB(16)? Vielhaber, Chacón, and Ceballos's paper "Friedman's 'Long Finite Sequences': The End of the Busy Beaver Contest" gives a 2450-state two-symbol busy beaver halting after at least n(4) steps, where n is Friedman's block subsequence function, but this is a very large jump up in state count from 14 states for f_ω+1(65536). (This paper has some mistakes with their (symbol,state count) notation for TMs, for example referring to Aaronson's and Yedidia's machine as a (7910,2) machine rather than a (2,7910) machine, so maybe the machine whose state count I wrote here is the wrong one.) C7X (talk) 22:00, 17 August 2024 (UTC)

Today i found some bounds on BB(20) and BB(21), though i'm not sure if they're new. $\Sigma (20)>f_{\omega +2}^{2}(21)$ due to 1LR0LR_0RJ1RG_0RD1LC_1RQ1RE_1LO0RQ_1LH1LF_0LC1LH_0LI0LF_1RD0LF_---0RK_0LM1LL_0LL1LM_1LE1LN_0LF0LM_0RP1LO_0LF0RQ_1RB1RQ_0RS1LA_1LT1RS_0LP0RR (bbch) and $\Sigma (21)>f_{\omega ^{2}}^{2}(4\uparrow \uparrow 341)$ due to 0LI0LF_0RJ1RG_0RD1LC_1RH1RE_1LO0RH_1LA1LF_0LC1LA_1RB1RH_1RD0LF_1LP0RK_0LM1LL_0LL1LM_1LE1LN_0RQ0LM_0RP1LO_1LR0RH_1LF1RQ_---0LS_1LH0LT_1LH1LU_0LE1LR (bbch).

The old googology wiki claims some other bounds, two of which are already implied by the bounds mentioned above, but $\Sigma (85)>f_{\varepsilon _{0}}(1907)$ and the bounds for more than 2 symbols seem to still be the best known.

Racheline (talk) 23:08, 17 August 2024 (UTC)

Racheline, congratulations on discovering a TM that crushes Graham's number. I was very impressed. but I think that in reality BB(8,2) will beat Graham's number. But it is unrealistic for a human to build such a machine. Only to search in the wild. Unfortunately. Nevertheless, congratulations again and further success!!! --Konkhra (talk) 03:29, 18 August 2024 (UTC)

And how about an article about BB(14)?--Konkhra (talk) 03:30, 18 August 2024 (UTC)

IMHO, beyond Graham's number I think we should only list highlights (if anything). Like first TM bigger than blah for various notable blah. Otherwise the churn on this page will be high and the quality low. But I'm open to other points of view. If we do extend this much further, I think maybe we should have a more rigorous process for getting new results demonstrated before they are added. --sligocki (talk) 02:57, 18 August 2024 (UTC)

Can you design very large champions as beat the $f_{\psi (\varepsilon _{\Omega +1})}(1000)$, and beat the $f_{\psi (\Omega _{\omega })}(1000)$, limit for BMS or beat Loader's number? --Jacobzheng (talk) 00:45, 17 September 2024 (UTC)

Later today I can try writing one (or at least starting to write one today), but my machine would likely have thousands of states. C7X (talk) 15:50, 16 September 2024 (UTC)

I now have two-symbol machines with the following running times. In order to squeeze the best possible results out of Bashicu matrix system, some machines have a different function applied to $n$ at each step (this function is what Bashicu calls the "activation function"), although at this scale it doesn't make too much of a difference.

Busy Beaver lower bounds using BM4

State count	Running time	Activation function
5889	$>f_{\psi (\varepsilon _{\Omega +1})}(1000)$ (using BMS to define FSes)	$n\mapsto n+1$
5894	$>f_{\psi _{0}(\Omega _{\omega })}(1000)$ (using BMS to define FSes)	$n\mapsto n+1$
5908	$>(0,0,0,0,0)(1,1,1,1,1)[2]$	$n\mapsto n+2$
5923	$>(0,0,0,0,0)(1,1,1,1,1)[5]$	$n\mapsto n+1$
5941	$>(0,0,0,0,0,0,0,0,0,0)(1,1,1,1,1,1,1,1,1,1)[10]$	$n\mapsto n+1$
5978	$>(\underbrace {0,0,\ldots ,0,0} _{889})(\underbrace {1,1,\ldots ,1,1} _{889})[894]$	$n\mapsto n+6$
6020	$>(\underbrace {0,0,\ldots ,0,0} _{N})(\underbrace {1,1,\ldots ,1,1} _{N})[N]$ where $N$ is $2^{2^{2^{2059}}}$	$n\mapsto n+5$

Edit: It turns out CatIsFluffy beat me to it! I don't know how many states the BMS machine has, but BB(1094) > Loader's number, now down to BB(1015). C7X (talk) 11:37, 4 October 2024 (UTC)

Who can design a Laver table q function level machine. --Jacobzheng (talk) 06:57, 13 February 2025 (UTC)

Me, probably. This 67-state TM should leave over q⁸¹(q(5)-2) 1s on the tape (maybe i have an off-by-one or off-by-two error in the exponent of q but it's still iterated quite a few times):

M = (
    ((1, 1, 1), (0, -1, 3)),
    ((0, -1, 2), (0, 1, 1)),
    ((1, 1, 0), (1, -1, 2)),
    ((0, -1, 4), (1, -1, 0)),
    ((0, -1, 2), (1, -1, 5)),
    ((0, 1, 26), (0, 1, 5)),
    ((1, -1, 57), (0, 1, 26)),
    ((0, 1, 38), (1, 1, 8)),
    ((0, 1, 9), (1, 1, 8)),
    ((0, 1, 62), (0, 1, 10)),
    ((0, -1, 16), (0, -1, 11)),
    ((1, -1, 12), (1, -1, 11)),
    ((0, 1, 15), (0, 1, 13)),
    ((1, 1, 14), (1, 1, 13)),
    ((0, -1, 16), (0, -1, 11)),
    ((0, 1, 10), (1, 1, 15)),
    ((1, -1, 33), (0, -1, 17)),
    ((1, -1, 18), (1, -1, 17)),
    ((0, -1, 19), (1, -1, 18)),
    ((0, -1, 20), (1, -1, 19)),
    ((0, 1, 22), (1, -1, 21)),
    ((1, 1, 21), (0, 1, 22)),
    ((0, 1, 23), (1, 1, 22)),
    ((1, -1, 24), (1, 1, 23)),
    ((1, -1, 30), (0, 1, 25)),
    ((1, -1, 26), (1, 1, 25)),
    ((0, 1, 6), (0, -1, 27)),
    ((0, -1, 28), (1, -1, 27)),
    ((0, -1, 29), (1, -1, 28)),
    ((1, -1, 20), (1, -1, 29)),
    ((1, 1, 32), (0, -1, 31)),
    ((1, -1, 32), (1, -1, 31)),
    ((0, 1, 7), (0, -1, 30)),
    ((0, -1, 34), (0, -1, 33)),
    ((0, -1, 34), (0, -1, 35)),
    ((0, 1, 37), (1, 1, 36)),
    ((0, 1, 36), (1, -1, 16)),
    ((0, 1, 37), (0, 1, 7)),
    ((0, 1, 39), (0, 1, 7)),
    ((0, -1, 44), (0, -1, 40)),
    ((0, -1, 41), (1, -1, 40)),
    ((1, 1, 42), (1, -1, 41)),
    ((0, 1, 43), (1, 1, 42)),
    ((1, 1, 39), (1, 1, 43)),
    ((0, -1, 45), (1, -1, 44)),
    ((0, -1, 47), (0, -1, 46)),
    ((1, -1, 45), (1, -1, 46)),
    ((1, -1, 47), (1, 1, 48)),
    ((0, -1, 49), (1, 1, 48)),
    ((0, 1, 56), (0, -1, 50)),
    ((0, 1, 49), (0, 1, 51)),
    ((1, 1, 52), (1, 1, 51)),
    ((0, -1, 55), (0, -1, 53)),
    ((1, -1, 54), (1, -1, 53)),
    ((0, 1, 51), (0, 1, 51)),
    ((0, -1, 50), (1, -1, 55)),
    ((1, -1, 57), (1, 1, 56)),
    ((1, -1, 61), (0, -1, 58)),
    ((1, 1, 59), (1, -1, 58)),
    ((0, -1, 60), (0, 1, 56)),
    ((1, 1, 61), (1, -1, 60)),
    ((1, -1, 66), (0, 1, 7)),
    ((0, 1, 63), (0, 1, 62)),
    ((0, 1, 63), (0, 1, 64)),
    ((0, -1, 65), (1, 1, -1)),
    ((0, -1, 65), (1, -1, 66)),
    ((0, -1, 40), (1, -1, 66))
)

(start from state 0)

It could probably be optimized a bit more, because there are two parts that do basically the same thing and could probably be joined together, but it would cost a few extra states to then differentiate between which of them it was supposed to be, and i don't have time to do that right now.--Racheline (talk) 18:56, 13 February 2025 (UTC)

BB(51) epsilon_0 champion

Can you show the transitions of BB(51) on Large champions transitions page? --Jacobzheng (talk) 03:24, 3 September 2024 (UTC)

Here are the transitions and description from Racheline:

Σ(51) > (f_ε0)^8(f_ω^ω^3(a lot)) > f_ε0+1(8)
M = (
0:     ((1, -1, 0), (0, -1, 1)),
1:     ((1, -1, 0), (1, 1, 2)),
2:     ((1, -1, 2), (0, -1, 4)),
3:     ((0, -1, 10), (1, -1, 4)),
4:     ((0, -1, 3), (0, -1, 5)),
5:     ((1, -1, 4), (1, 1, 6)),
6:     ((1, -1, 7), (0, -1, 15)),
7:     ((0, -1, 8), (1, -1, 7)),
8:     ((0, -1, 9), (1, -1, 7)),
9:     ((1, 1, 11), (1, -1, 9)),
10:    ((0, -1, 20), (0, -1, 17)),
11:    ((0, 1, 12), (1, 1, 11)),
12:    ((0, 1, 13), (1, 1, 13)),
13:    ((1, -1, 14), (1, 1, 12)),
14:    ((0, -1, 6), (1, -1, 10)),
15:    ((0, -1, 16), (1, -1, 16)),
16:    ((1, -1, 20), (1, -1, 15)),
17:    ((0, -1, 18), (1, -1, 18)),
18:    ((1, 1, 19), (1, -1, 17)),
19:    ((1, -1, 19), (1, -1, 20)),
20:    ((0, -1, 50), (0, -1, 21)),
21:    ((0, 1, 43), (0, -1, 9)),
22:    ((0, 1, 22), (1, 1, 23)),
23:    ((1, 1, 26), (0, -1, 24)),
24:    ((1, -1, 25), (0, -1, 24)),
25:    ((1, 1, 25), (1, 1, 22)),
26:    ((0, 1, 50), (0, 1, 27)),
27:    ((1, 1, 26), (1, -1, 35)),
28:    ((0, 1, 29), (0, 1, 30)),
29:    ((0, -1, 4), (1, 1, 28)),
30:    ((1, -1, 31), (1, -1, 0)),
31:    ((0, -1, 32), (1, -1, 33)),
32:    ((0, -1, 33), (1, -1, 31)),
33:    ((0, -1, 34), (0, -1, 35)),
34:    ((0, -1, 37), (1, -1, 33)),
35:    ((1, 1, 36), (1, 1, 38)),
36:    ((0, 1, 37), (1, 1, 28)),
37:    ((0, -1, 29), (1, 1, 36)),
38:    ((1, 1, 38), (1, 1, 39)),
39:    ((0, 1, 38), (1, 1, 40)),
40:    ((0, 1, 41), (1, -1, 42)),
41:    ((1, -1, 49), (1, 1, 40)),
42:    ((1, 1, 36), (0, -1, 42)),
43:    ((0, 1, 44), (1, 1, 44)),
44:    ((1, -1, 45), (1, 1, 43)),
45:    ((0, -1, 46), (1, -1, 46)),
46:    ((0, 1, 22), (1, -1, 45)),
47:    ((1, -1, 41), (1, -1, 47)),
48:    ((0, -1, 47), (0, -1, 49)),
49:    ((1, -1, 22), (1, -1, 48)),
50:    ((0, -1, 48), (1, 1, halt))
)
 
(start from state 30)

I haven't investigated it yet. Sligocki (talk) 14:27, 3 September 2024 (UTC)

It directly simulates Address Notation, which is a different way to write Primitive Sequence System (PrSS for short, it's 1-row Bashicu Matrix System). Here are the expansion rules of Address Notation:

Given a sequence $S$ of natural numbers, to compute its expansion, start by letting $c$ be the last element of $S$. If $c=0$, then $S$ is a successor and its predecessor is $S$ without the last element. Otherwise, find the last element $r$ of $S$ which is less than $c$. Decrease $c$ by $1$, and let $B$ be everything in this new sequence after $r$. Append infinitely many copies of $B$.

Since the sequences are ordered lexicographically and each element decreases by $1$ until it is $0$, for any fundamental sequence system where each $S[n]$ is formed by taking an initial subsequence of the expansion of $S$ and changing the last element of that subsequence to a smaller or equal natural number, the ordinal notation given by the fundamental sequence system is the same. If i remember correctly, the TM simulates a variant $h$ of the Hardy Hierarchy with a fundamental sequence system where the FS of each standard $S$ contains all sequences longer than $S$ formed this way from its expansion (except for the first one or two).

Specifically,

$h_{0}(n)=n+c_{0}$

$h_{\alpha +1}(n)=h_{\alpha }(n+c_{1})$

$h_{\alpha }(n)=h_{\alpha [n]}(c_{2})$ for limit $\alpha$

$h_{\varepsilon _{0}}(n)=h_{(0,\lfloor {\frac {n+c_{3}}{2}}\rfloor )}(c_{4})=h_{\omega \uparrow \uparrow \lfloor {\frac {n+c_{3}}{2}}\rfloor }(c_{4})$

for some constants $c_{0},c_{1},c_{2},c_{3},c_{4}$ for which the hierarchy is not degenerate (the constants can be deduced easily from the TM's space-time diagram). In particular, the non-degeneracy means that for most FGHs $f$ with "natural" FS systems, we will have $f_{\alpha +1}(n)<h_{\omega ^{\alpha +1}}(n+k)$ for some small constant $k$ (depending on $f$), and as long as the FGH's FS system has $\varepsilon _{0}[n]\leq \omega \uparrow \uparrow (n+c)$ for some constant $c$, we have $f_{\varepsilon _{0}}(n)<h_{\varepsilon _{0}}(2(n+c)+k)$ for some small constant $k$ (also depending on $f$. For example, the Wainer Hierarchy is one of these "natural" FGHs (and one of the most well-known ones at this level), and if we extend it to include $f_{\varepsilon _{0}}$ and $f_{\varepsilon _{0}+1}$ with the FS $\varepsilon _{0}[n]=\omega \uparrow \uparrow n$, it does indeed satisfy $f_{\varepsilon _{0}}(n)<h_{\varepsilon _{0}}(2n+k)$ for small $k$, which means that since the TM computes $h_{\varepsilon _{0}}^{8}(n)$ for a large $n$, its output is larger than $f_{\varepsilon _{0}+1}(8)$. Racheline (talk) 19:06, 3 September 2024 (UTC)

I think the bbchallenge can search BB(7) and BB(4,3) in the wild. --Jacobzheng (talk) 14:56, 30 October 2024 (UTC)

I have thought about writing a program that searches for Ackermann's worm-like behavior of TMs (or at least a program for exponential behavior), but I wouldn't be sure how to do it. C7X (talk) 22:07, 30 October 2024 (UTC)

Cloud search for busy beavers

We still lack a website for cloud search busy beaver functions. --Jacobzheng (talk) 07:07, 15 December 2024 (UTC)

In the case of distributed computing projects like Catalogue and Great Internet Mersenne Prime Search, it seems like those are distributed to divvy up a large finite amount of computation. I don't know much about searching for Busy Beavers (e.g. if there is such a thing as an automated process for finding accelerated simulators) but would distributed finite computation be able to help reduce holdout lists? C7X (talk) 09:05, 15 December 2024 (UTC)

It may be able to search the busy beaver domain BB(7) or even larger more quickly. Jacobzheng (talk) 13:38, 15 December 2024 (UTC)

Certainly it could do something like direct simulation quickly, but is there a known way to automate more advanced techniques to look for long-running machines? C7X (talk) 22:17, 15 December 2024 (UTC)

questions like these should be asked on discord. Few people look at this page.--Konkhra (talk) 06:10, 16 December 2024 (UTC)