2024/05/22/bb-3-4-a14

[utterances-bot]

BB(3, 4) > Ack(14) | sligocki

Pavel has found a 3-state 4-symbol TM which can compute an “Ackermann-level” function and halts with exactly

https://www.sligocki.com//2024/05/22/bb-3-4-a14.html

[LegionMammal978]

Placing this value within the fast-growing hierarchy, we have f₁₆(2) < 2 ↑¹⁵ 4 < σ < (2 ↑¹⁴)³ 5 < f₁₆(3), or more coarsely, f_ω(15) < σ < f_ω(16).

[bollu]

I am curious which discord group this is happening in!

[sligocki]

Pavel found another Ackermann TM:

1RB1RZ1LA2RB_1RC3RC1LA2LB_2LB2RC1LC3RB`

3^n <A 1^k 2^c 0^inf  -->  <A 1^k 2^x 0^inf  for x = g_k^n(c)

g_1(y) = y + 2
g_{k+1}(y) = g_k^{y+1}(1)

0^inf A> 0^inf  --(182)-->
0^inf 1 3^2 <A 1^13 2 0^inf  -->
0^inf 1 <A 1^13 2^x 0^inf   for x = g_{13}^2(1)  --(1)-->
0^inf 1 Z> 1^13 2^x 0^inf

Score: g_13^2(1) + 14

I believe (but haven't checked carefully) that:

g_k(y) = 2{k-2}(y+3) - 3
g_k^x(1) = g_{k+1}(x-1) = 2{k-1}(x+2) - 3

so, Score = 2{12}4 + 11 > Ack(11)

(Where I am adopting the notation a{k}b for $$a \uparrow^k b$$)

[sligocki]

I am curious which discord group this is happening in!

Ah, sorry I should have clarified. It's the bbchallenge Discord: See public invite link at top right of https://bbchallenge.org/

[sligocki]

Permutations of 1RB1RZ1LA2RB_1RC3RC1LA2LB_2LB2RC1LC3RB:

0^inf B> 0^inf  --(84)--> 0^inf 1 3^2 <A 1^7 2 0^inf
0^inf C> 0^inf  --(18)--> 0^inf 1 3^2 <A 1^1 2 0^inf

So these score g_7^2(1) + 8 = 2{6}4 + 5 and g_1^2(1) + 2 = 7 respectively.

[sligocki]

Actually, these TMs are all adjacent. If you take 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC (the main Ack(14) TM) and replace A0->2LB (and then convert into TNF) you get 1RB1RZ1LA2RB_1RC3RC1LA2LB_2LB2RC1LC3RB (the Ack(11) TM). I've looked through all other options for A0->??? and none of the rest seem to work.