BB(2, 5) > 7.3 x 10^19016

[uni...@fu-solution.com]

well, it's quite surprising: 1RB2LB4LB3LA1RZ_1LA3RA3LB0LB0RA

* last configuration:
```
3^ẽ19016⋮124 1 3^82 1 3^3 1 3 1 Z> 0^1249 2 3^9 1 2^2 1 0^185 2 3^6 1 2
1 0^21 2 1 2 4 2 0^2 2 1 4 0^8 2 1 2^2 1 0^93 2 1 2^2 {2 1}^2 4 0^2 2 1
4 0^8 2 1 2^2 1 0^24 2 1 2 4 2 0^55 2 3^3 1 2^2 1 0^12 2 1 4 0^2 {2 1}^2
0^6 2 1 4 0^17 2 1 2 4 2^6 0^55 2 3^6 1 4 2 0^2 2 1 4 2 0^32 2 1 2^3 1
0^12 2 1 4 2 0^2 2 1 4 0^8 2 1 2^2 1 0^15 2 1 2^2 1 0^24231 2 1 2 0^11 2
1 4 1 0^78 2 1 2^2 1 0^8 2 3^3 1 4 0^76 2 3^6 1 2 1 0^480 2 1 2^4 {2
1}^2 4 0^8 {2 1}^2 0^3 {2 1}^2 0^21 2 1 2 4 2 0^5 2 1 2 4 2^2 0^7 2 3^3
1 4 2^5 0^8 2 1 4 2^2 0^2 {2 1}^5 4 0^8 {2 1}^2 0^3 2 1 2^2 1 0^14 2 3^3
1 2 1 0^35 2 3^3 1 2 4 0^2 {2 1}^4 0^9 2 1 4 2 0^364 2 3^6 1 4 0^19 2
3^6 1 2 4 0^2 2 1 4 0^107 2 1 2^2 4 2^4 0^31 2 3^3 1 4 0^97 {0^2 2 1}^2
2 0^3 2 1 4 2 0^2 2 1 4 0^295 2 3^9 1 4 0^5608 2 3^6 1 0^2 2 1 4^2 0^11
2 1 2^2 1 0^5 2 3^3 1 4 2^2 {0^2 2 1 4}^2 2^3 0^5 {2 1}^2 0^6 2 1 4 0^2
{2 1}^2 0^51 2 1 2^2 {2 1}^2 4 0^2 2 1 4 2 0^56 2 1 2^3 1 0^18 2 1 4
{0^2 {2 1}^3 4}^2 2^4 0^19 2 3^3 1 4 0^5 {2 1}^4 0^116 2 3^6 1 4 0^5 {2
1}^2 0^3 {2 1}^4 0^3 2 1 4 0^10 2 3^3 1 {2 1}^2 4 0^23 2 1 2^2 1 0^3 2 1
4 2 0^11 2 1 2 4 2 0^2 {2 1}^2 0^180702 2 1 2^2 0^5 2 1 4 0^2 2 1 2 0^3
2 1 4 2^2 0^481 2 3^6 1 2 4 0^2 {2 1}^3 4 2 0^5 2 1 4 2^3 0^11 2 1 2^2 1
0^6 2 1 2^2 1 0^23 2 3^3 1 2 1 0^12 2 1 2 4 0^47 2 1 2^2 1 0^9 2 1 4 2
0^5 {2 1}^2 0^161 2 3^6 1 {2 1}^3 0^78 2 1 2^2 4 2 0^13 2 3^3 1 4 0^11
{2 1}^2 0 {0^2 2 1 4}^2 0^22 2 3^3 1 {2 1}^2 4 0^34 2 3^3 1 2 1 0^3 2 1
4 2 0^5 2 1 4 0^2 {2 1}^2 0^5 2 3^3 1 2 1 0^3 2 1 4 0^2 {2 1}^2
```

* originally "announced" on bbchallenge.org discord:
https://discord.com/channels/960643023006490684/960643023530762341/1132942290302795867

* invite link: https://discord.gg/3uqtPJA9Uv - come! we have cookies and
holdouts to solve!

[nichol...@gmail.com]

Wow! This is really shocking. I have confirmed the result, but it wasn't easy. On my modest desktop, it takes Shawn's simulator almost six minutes to run, and on my own simulator, more than 18 minutes. That's not great! Clearly there's some grave inefficiency in my prover.

Is there any sort of macro configuration that makes it go faster? Does anyone have any insight into what it's doing?

[nichol...@gmail.com]

Okay, I figured out the grave inefficiency, and now I'm down to 77 seconds :)

I couldn't find any block size that works, but a 2-cell backsymbol macro helps a lot.

[Shawn Ligocki]

Great find Pavel! Wow, Busy Beaver's just love to trick us like this: First place 2x5 machine: 10^19016, second place: 10^352!

I can confirm this record. As Nick mentioned, my simulator takes ~5min to run this. The final step and score counts I get are:

Steps:    ~10^38_033.81523
Nonzeros: ~10^19_016.86803

On Tue, Jul 25, 2023 at 3:54 PM nichol...@gmail.com <nichol...@gmail.com> wrote:

Okay, I figured out the grave inefficiency, and now I'm down to 77 seconds :)

I couldn't find any block size that works, but a 2-cell backsymbol macro helps a lot.

--
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/acee61ae-80e1-4f2f-a025-b71aadda5888n%40googlegroups.com.

[Pascal Michel]

I give here some analyses on this machine.

We have  00(A0)0 --( 4 )--> (A0)121, and then, for all n, k >= 0,

(a) 0^(k + 2) (A0) 1 0^(2k + 1) 2 --(6k^2 + 19k + 10)--> (A0)10^(3k)2 3^3

(b) 0^(k + 2) (A0) 10^(2k) 21 --(6k^2 + 19k + 12)--> (A0)10^(3k + 1) 212

(c) 0^(k + 2) (A0) 10^(2k) 23^(n + 1)122 --(6k^2 + 19k + 4n + 30)--> (A0)10^(3k + 2) 21 0^n 214

(d) 0^(k + 2) (A0) 10^(2k) 23^(n + 1) 12 0^2 --(6k^2 + 19k + 4n + 32)--> (A0) 10^(3k + 2) 21 0^n 2121

(e)0^(k + 2) (A0) 10^(2k) 23^(n + 1) 1 0^2 --(6k^2 + 19k + 4n + 28)--> (A0)10^(3k + 1) 2 3^(n + 4) 1

(f) 0^(k + 2)(A0)10^(2k) 23^(n + 2) 102 --(6k^2 + 19k + 4n + 32)--> (A0)10^(3k + 2) 21 0^n 2 3^3

I don't know if more types of transitions are necessary, and I don't know the final transition.
You see that there is a Collatz-like behavior

The total number of transitions is approximately 107989.

I guess that s(M) is approximately (2/3)sigma(M)^2, but without proof.

[Pascal Michel]

There is a mistake in the previous mail.

Using the values given by Shawn, It is easy to see that s(M) is approximately (5/6) sigma(M)^2

[Pascal Michel]

Another mistake in the previous mail!

The correct fact is that s(M) is approximately (6/5) sigma(M)^2 

[Shawn Ligocki]

Pascal, you inspired me to dig a little more into this TM! I also found it hard to characterize the behavior in a concise way, but here is the best analysis I have been able to find so far:

A(a, b, c, d) ... = 0^inf <A 1 0^a 2 333^b 1 0^c 2 333^d ...

A(2k+1, b,   c,   d)  ->  A(3k,   b+1, c,    d)
A(2k,   b+1, c+2, d)  ->  A(3k+1, b+2, c,    d)
A(2k,   b+1, 1,   d)  ->  A(3k+2, 0,   3b+1, d+1)

A(2k, 0, c, d) -> A(3k+1, 0, 0, 0) 0^c 2 3^3d

A(2k, b+1, 0, 0) 00 -> A(3k+2, 0, 3b+2, 0) 121
A(2k, b+1, 0, 0) 1  -> A(3k+2, 0, 3b+2, 0) 12
A(2k, b+1, 0, 0) 2  -> A(3k+2, 0, 3b+2, 0) 14

A(2k, b+1, 0, d+1) 121 -> A(3k+2, 0, 3b+3, 0) 1 0^3d+2 212
A(2k, b+1, 0, d+1) 122 -> A(3k+2, 0, 3b+3, 0) 1 0^3d+2 214
A(2k, b+1, 0, d+1) 14  -> Halt!

Start (at step 16): A(1, 0, 0, 0) 0^inf = 0^inf <A 10212 0^inf

Some notes are in order here:

1. By (A(2k, b+1, 0, 0) 00 -> A(3k+2, 0, 3b+2, 0) 121) I mean that if the first two symbols after the A() expression (where the ... are listed in the definition) are 00, then replace those with 121 (in addition to adjusting the A() parameters).
2. These rules are NOT exhaustive, they do not include rules for situations that could (in theory) occur like (A(2k, b+1, 0, d+1) 123) or (A(2k, b+1, 0, 0) 02), etc. However, none of these occur in practice while simulating from a blank tape. I don't think an exhaustive list is possible as the (A(2k, b+1, 0, d+1) 123) case would lead to much more complicated behavior.
3. In practice, while using these rules, you only need to keep track of the nearest 3 symbols on the right (since no rule looks at more than 3 symbols on the right and they all strictly increase the number of symbols on the right). Again, this is specific to the trajectory starting from a blank tape, from an arbitrary starting point, I don't think any such restriction is possible in general

Starting at (A(1, 0, 0, 0)) it takes 107,994 iterations to halt! The last config before halting is (A(~10^19_016.69, 27, 0, 1) 14 ...).

If you break down the iterations by which rule they use we see:

54143  (2k+1, b, c, d)
53415  (2k, b+1, c+2, d)
  221  (2k, 0, c, d)
   60  (2k, b+1, 0, 0) 2
   54  (2k, b+1, 0, 0) 00
   48  (2k, b+1, 1, d)
   47  (2k, b+1, 0, 0) 1
    3  (2k, b+1, 0, d+1) 122
    2  (2k, b+1, 0, d+1) 121
    1  (2k, b+1, 0, d+1) 14

The overwhelming majority of iterations are spent dealing with the situation where c is large. Specifically, this TM has one triumphant moment where c grows to a maximum of 60,002.

If we focus only on this behavior for large c, we see it's a much simpler second-level Collatz-like behavior:

A(2k+1, b,   c,   d)  ->  A(3k,   b+1, c,    d)
A(2k,   b+1, c+2, d)  ->  A(3k+1, b+2, c,    d)

So, we are iterating the Collatz-like function

2k+1 -> 3k

2k   -> 3k+1

incrementing b on each iteration and reducing c by 2 every time we follow the even rule. This leads to growth approximately like:

A(a, b, c, d) -> A(~(3/2)^c a, ~b+c, 0 or 1, d)

That is to say, we will iterate approximately c times, each time increasing a by about 3/2 and b by 1 until c is less than 2. At this point there are several possible rules each of which lead to remarkably similar configurations:

A(2k, b+1, 1, d  )     -> A(3k+2, 0, 3b+1, d+1)
A(2k, b+1, 0, 0  ) 00  -> A(3k+2, 0, 3b+2, 0) 121
A(2k, b+1, 0, 0  ) 1   -> A(3k+2, 0, 3b+2, 0) 12
A(2k, b+1, 0, 0  ) 2   -> A(3k+2, 0, 3b+2, 0) 14
A(2k, b+1, 0, d+1) 121 -> A(3k+2, 0, 3b+3, 0) 1 0^3d+2 212
A(2k, b+1, 0, d+1) 122 -> A(3k+2, 0, 3b+3, 0) 1 0^3d+2 214

And here's where the interesting bit happens. If 3k+2 is even then we apply

A(2k, 0, c, d) -> A(3k+1, 0, 0, 0) 0^c 2 3^3d

and c gets reset to 0 ending the big-c fun. But if 3k+2 is odd then we apply

A(2k+1, b,   c,   d)  ->  A(3k,   b+1, c,    d)

And we start over again with a c value ~3x bigger than the previous run. The secret to how this TM runs for so long is basically that it eventually gets lucky and hits the following sequence:

   553   A(     2.799e+97,     0,       0,     0)   000
   558   A(     2.126e+98,     0,      11,     0)   121

   569   A(    1.839e+100,     0,      28,     1)   121
   600   A(    5.289e+105,     0,      90,     0)   100
   684   A(    3.274e+120,     0,     248,     0)   120
   931   A(    1.022e+164,     0,     737,     0)   122
 1_683   A(    2.693e+296,     0,   2_251,     1)   122
 3_912   A( ~10^688.93760,     0,   6_682,     2)   122
10_599   A(~10^1_866.4598,     0,  20_058,     0)   100
30_601   A(~10^5_388.6372,     0,  60_002,     0)   120
90_837   A(~10^15_995.670,     0, 180_704,     0)   122
90_838   A(~10^15_995.846,     0,       0,     0)   000

That is, it lands on an odd number 9 times (each time increasing c roughly 3x) before hitting the first even (and thus resetting c). This single lucky streak takes the tape size from 10^98 to 10^16k. The TM hits a couple more lucky streaks later:

  91_124   A(~10^16_046.20849,     0,     0,     0)   200
 91_128   A(~10^16_046.91285,     0,     8,     0)   140
 91_138   A(~10^16_048.67376,     0,    26,     0)   124
 91_161   A(~10^16_052.72386,     0,    65,     0)   122
 91_226   A(~10^16_064.16979,     0,   190,     1)   122
 91_434   A(~10^16_100.79678,     0,   621,     0)   100
 92_054   A(~10^16_209.97336,     0, 1_855,     1)   100
 93_925   A(~10^16_539.44010,     0, 5_608,     2)   100
 93_926   A(~10^16_539.61619,     0,     0,     0)   000

and

 94_881   A(~10^16_707.78335,     0,      0,     0)   000
 94_885   A(~10^16_708.48771,     0,      8,     0)   121
 94_896   A(~10^16_710.42472,     0,     29,     0)   122
 94_930   A(~10^16_716.41182,     0,     97,     1)   122
 95_024   A(~10^16_732.96440,     0,    277,     2)   122
 95_328   A(~10^16_786.49614,     0,    907,     3)   122
 96_223   A(~10^16_944.09782,     0,  2_680,     4)   122
 98_912   A(~10^17_417.60721,     0,  8_064,     0)   100
106_991   A(~10^18_840.24849,     0, 24_233,     0)   120
106_992   A(~10^18_840.42458,     0,      0,     0)   000

but they aren't able to make nearly as much impact.

Finally, the TM finds it's way to the halting transition shortly thereafter:

107_954   A(~10^19_009.82438,     0,     0,     0)   200
107_957   A(~10^19_010.35265,     0,     5,     0)   140
107_966   A(~10^19_011.93747,     0,    22,     1)   140
107_993   A(~10^19_016.69194,    27,     0,     1)   140

Note: This TM has to follow a narrow path in order to halt, specifically, it must apply the following transitions in order:

A(2k, 0,   c+1, d)       ->  A(3k+1, 0, 0,    0) 0^c+1 2 3^3d

A(2k, 0,   0,   0)       ->  A(3k+1, 0, 0,    0) 2
A(2k, b+1, 0,   0) 2     ->  A(3k+2, 0, 3b+2, 0) 14

A(2k, b+1, 1,   d)       ->  A(3k+2, 0, 3b+1, d+1)

A(2k, b+1, 0,   d+1) 14  ->    Halt!

applying only a very limited set of transitions between each of these or else it falls off of the path and must restart eventually.

PS: My rules are basically a superset of Pascal's. Specifically, Pascal's rules (a-f) correspond to mine in this way:

(a)  A(2k+1, b,   c,   d)  ->  A(3k,   b+1, c,    d)

(b)  A(2k, 0, c, d) -> A(3k+1, 0, 0, 0) 0^c 2 3^3d   (When c = 0)
(c)  A(2k, b+1, 0, 0) 2  -> A(3k+2, 0, 3b+2, 0) 14

(d)  A(2k, b+1, 0, 0) 00 -> A(3k+2, 0, 3b+2, 0) 121

(e)  A(2k,   b+1, c+2, d)  ->  A(3k+1, b+2, c,    d)

(f)  A(2k,   b+1, 1,   d)  ->  A(3k+2, 0,   3b+1, d+1)

To view this discussion on the web visit https://groups.google.com/d/msgid/busy-beaver-discuss/45bd4174-5c5c-4503-accb-0c598f370334n%40googlegroups.com.