BB(3, 4) > Ack(14)

[Shawn Ligocki]

Pavel has found a 3-state 4-symbol TM which can compute an “Ackermann-level” function. See my analysis:

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

Remarkably, we can compute its sigma value precisely = (2 ↑^15 5) + 14 (where ↑^15 are 15 Knuth up-arrows).

I think this is a remarkable step forward in the giant scores of TMs.

[Tristan Stérin]

Amazing work, thank you!

--
You received this message because you are subscribed to the Google Groups "Busy Beaver Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to busy-beaver-dis...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/CADhnJ7BRGTd8oOiDwwNc2TeraZCCV9a9jOYpARJHDe6G_TKXYA%40mail.gmail.com.

[nichol...@gmail.com]

Wow, this is very cool!

I can't confirm that it halts, but I can at least confirm that it does at some point execute an exponential rule an exponential number of times. The only other program that does this that I know of is the 10-state Green machine (https://www.sligocki.com/2023/10/19/greens-machines.html). So personally I find it plausible that this new one really does have Ackermann-like behavior as claimed. (I will attempt confirm all the way.)

Some facts about the new champ:

1. The control flow is fairly simple. State B seems to be the main dispatcher state, passing control to A and C. Meanwhile, neither A nor C know about each other; they only pass control back to B. There are no zero-reflexive instructions (that is, never X0 -> ..X).

2. It never prints a blank. This make sense: there are infinitely many blanks on the tape, so why waste any instructions making more? If you need a blank, just go to the edge of the marks and rope in a new one. I conjecture that this will always be true for champs with colors >= 4. Notice that the previous 3/4 champ, which produces ~10^^2048 marks (and was also discovered by Pavel), does print blanks. According to my conjecture, this would suggest it was suboptimal, and that is indeed the case.

3. Similarly, every instruction either changes the state or changes the color. This is something else we might expect from a champion, since an instruction that changes neither the state nor the color seems lazy. Again, the previous 3/4 champ contained the lazy instruction A3 -> 3LA, suggesting suboptimality. As a notable counterexample, the presumed 5/2 champ has not one, but two lazy instructions (B1 -> 1RB and D1 -> 1LD). But other than that, no current champs AFAIK have any lazy instructions. Maybe this conjecture is true for "sufficiently many" states and colors.

[Shawn Ligocki]

Update, Pavel found another (slightly smaller) Ackermann TM that I am able to verify:

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

[Shawn Ligocki]

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.

[nichol...@gmail.com]

I need to correct my previous remark. In fact, the current 2/5 champ, which leaves ~10^19017 marks and was also discovered by Pavel, contains a lazy instruction (A3 -> 3LA). It also contains two erase instructions (changing mark to blank). So maybe these sorts of conjectures are all garbage. (Or alternatively, the conjectures could be true, and the real 2/5 champ is yet to be found.)

[Shawn Ligocki]

I have worked out the approximate runtime for this TM. My estimation is s(M) ~= 4/3 sigma(M)^2. As with many champions it takes O(N^2) time to expand to N size, in this case the coefficient seems to be 4/3. Of course, when we are talking about numbers this large, squaring them makes almost no change, so all bounds here apply just as well to the step count.

Here is my sketch for the reasoning:

Define t_k(n, e) as the number of steps in the rule B(k+1, n, e) --> B(k+1, 0, g_k^n(e))

Then I compute:

• t_k(0, e) = 0
• t_0(n, e) = 4n(n-1) + n(8e+9)
• t_k(n, e) = t_{k-1}(2e+2, 0) + t_k(n-1, g_k(e)) + (2k+4 + (2e+1)(2k+3))

Focussing on e=0 and filtering out the low order factors we get:

• t_0(n, 0) = 4 n^2 + 5n ~= 4 n^2 = 4 (g_0^n(0))^2
• t_k(n, 0) ~= sum_{x=0}^{n-1} t_{k-1}(2 g_k^x(e) + 2, 0)

For k=1, we must consider the entire sum (since 2^{n-1}/2^n = 1/2):

• t_1(n, 0) ~= sum_{x=0}^{n-1} 4 (2 g_1^x(0) + 2)^2 = 4 sum (2^{x+2} - 2)^2 ~= 4 sum 4^{x+2} = 4 (4^{n+2} - 4)/3 ~= 4/3 4^{n+2}
  Recall: 2 g_1^n(0) + 4 = 2^{n+2} so 4 (g_1^n(0))^2 ~= 4^{n+2}
  so: t_1(n, 0) ~= 16/3 (g_1^n(0))^2
  Let X = 16/3

For k > 1, the high term dominates (since 2^^{n-1} / 2^^n -> 0) so we can see by induction that:

• t_k(n, 0) ~= X (g_k^n(0))^2
• t_k(n, 0) ~= t_{k-1}(2 g_k^{n-1}(0) + 2, 0) ~= X [g_{k-1}^{2 g_k^{n-1}(0) + 2}(0)]^2 = X [g_k(g_k^{n-1}(0))]^2 = X (g_k^n(0))^2

Finally,

• s(M) ~= t_{15}(3, 0) ~= 16/3 (g_{15}^3(0))^2
• sigma(M)^2 = (2 g_{15}^3(0) + 18)^2 ~= 4 (g_{15}^3(0))^2

So s(M) / sigma(M)^2 ~= 4/3

On Wed, May 22, 2024 at 3:34 PM Shawn Ligocki <slig...@gmail.com> wrote:

[Pascal Michel]

I have computed that

t_1(n,e) = (16(4^n - 1)/3) e^2 + ((4^(n + 3) - 28)/3 - 3 x 2^(n + 2)) e + (4^(n + 3) + 8)/3 - 3 x 2^(n + 3) - 3n