Talk:Champions

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)

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)
n0 = 21
n1 = 42
n2 = 46
M = (
    ((1, -1, 0), (0, -1, 1)),
    ((1, -1, 0), (1, 1, 2)),
    ((1, -1, 2), (0, -1, 4)),
    ((0, -1, 10), (1, -1, 4)),
    ((0, -1, 3), (0, -1, 5)),
    ((1, -1, 4), (1, 1, 6)),
    ((1, -1, 7), (0, -1, 15)),
    ((0, -1, 8), (1, -1, 7)),
    ((0, -1, 9), (1, -1, 7)),
    ((1, 1, 11), (1, -1, 9)),
    ((0, -1, 20), (0, -1, 17)),
    ((0, 1, 12), (1, 1, 11)),
    ((0, 1, 13), (1, 1, 13)),
    ((1, -1, 14), (1, 1, 12)),
    ((0, -1, 6), (1, -1, 10)),
    ((0, -1, 16), (1, -1, 16)),
    ((1, -1, 20), (1, -1, 15)),
    ((0, -1, 18), (1, -1, 18)),
    ((1, 1, 19), (1, -1, 17)),
    ((1, -1, 19), (1, -1, 20)),
    ((0, -1, n2 + 4), (0, -1, 21)),
    ((0, 1, n1 + 1), (0, -1, 9)),

    ((0, 1, n0 + 1), (1, 1, n0 + 2)),
    ((1, 1, n0 + 5), (0, -1, n0 + 3)),
    ((1, -1, n0 + 4), (0, -1, n0 + 3)),
    ((1, 1, n0 + 4), (1, 1, n0 + 1)),
    ((0, 1, n2 + 4), (0, 1, n0 + 6)),
    ((1, 1, n0 + 5), (1, -1, n0 + 14)),
    ((0, 1, n0 + 8), (0, 1, n0 + 9)),
    ((0, -1, 4), (1, 1, n0 + 7)),
    ((1, -1, n0 + 10), (1, -1, 0)),
    ((0, -1, n0 + 11), (1, -1, n0 + 12)),
    ((0, -1, n0 + 12), (1, -1, n0 + 10)),
    ((0, -1, n0 + 13), (0, -1, n0 + 14)),
    ((0, -1, n0 + 16), (1, -1, n0 + 12)),
    ((1, 1, n0 + 15), (1, 1, n0 + 17)),
    ((0, 1, n0 + 16), (1, 1, n0 + 7)),
    ((0, -1, n0 + 8), (1, 1, n0 + 15)),
    ((1, 1, n0 + 17), (1, 1, n0 + 18)),
    ((0, 1, n0 + 17), (1, 1, n0 + 19)),
    ((0, 1, n0 + 20), (1, -1, n0 + 21)),
    ((1, -1, n2 + 3), (1, 1, n0 + 19)),
    ((1, 1, n0 + 15), (0, -1, n0 + 21)),

    ((0, 1, n1 + 2), (1, 1, n1 + 2)),
    ((1, -1, n1 + 3), (1, 1, n1 + 1)),
    ((0, -1, n1 + 4), (1, -1, n1 + 4)),
    ((0, 1, n0 + 1), (1, -1, n1 + 3)),

    ((1, -1, n0 + 20), (1, -1, n2 + 1)),
    ((0, -1, n2 + 1), (0, -1, n2 + 3)),
    ((1, -1, n0 + 1), (1, -1, n2 + 2)),
    ((0, -1, n2 + 2), (1, 1, -1))
)
 
(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)