New 2-state 5-symbol champion!

[Daniel Yuan]

Hello, this morning I have discovered a new BB(2, 5) champion, dethroning the old champion https://bbchallenge.org/1RB2LB4LB3LA1RZ_1LA3RA3LB0LB0RA with a sigma of >7.3 × 10^19016 steps!

The TM is https://bbchallenge.org/1RB3LA4RB0RB2LA_1LB2LA3LA1RA---, and the details of how it works explained on discord: https://discord.com/channels/960643023006490684/1084047886494470185/1254842225980997793

But the gist is that the TM is part bouncer and part counter, but the counter can overflow, in which case the bouncer ends up being the counter. Since usually by that time, the size bouncer becomes an exponental of the size of the counter, having the bouncer turn into the counter essentially shoves whatever size the tape was to the exponent. This effect happens 3-4 times before the mod 3 value becomes the right condition to halt. At the end, both the sigma and step score can be bounded below by 2^^7 or 10^^4.

[Shawn Ligocki]

A few details for those who don't have access / want to look on Discord. At a high level, this TM satisfies the following rules:

Counter Rules:

• 01 11^x <A 23^y 00 -> 11 01^x <A 23^y 21
  
• 01 11^x <A 23^y 21 -> 11 01^x <A 23^y 22
• 01 11^x <A 23^y 22 -> 11 01^x <A 23^y 23

In other words, each iteration, the left counts up 1 in a binary counter (using "01" for 0 and "11" for 1) while the right keeps track of the number of iterations modulo 3 (using the final value of "21", "22" or "23") and grows every 3 iterations.

This continues until the counter "overflows" and depending upon the mod on the right side it has one of 3 possible behaviors.

Overflow Rules:

• 0^inf 11^x+2 <A 23^y+2 0^inf    -> 0^inf 11 01^x 11 01^y 11^2 01 <A 21 0^inf
  
• 0^inf 11^x+2 <A 23^y+2 21 0^inf -> 0^inf 11 01^x 11 01^y 11 01^3 <A 21 0^inf
• 0^inf 11^x+1 <A 23^y+1 22 0^inf -> 0^inf 11 01^x 11^y+2 1 Z> 1 0^inf
  

I have confirmed all of the above rules in my inductive validator: https://github.com/sligocki/busy-beaver/commit/3189833014f1b2442d4ffe91c6e1d7fdb574675a

At step 2430 it is in config "0^inf 11^7 <A 23^17 21 0^inf" and Daniel reports that it proceeds to overflow 5 times with the last one hitting the halt rule (I have not confirmed this behavior yet myself). The penultimate config reported by Daniel is:

0^inf [11] [01]^(a+b+c+31) [11]^(d+1) 4 <B 1 0^inf

Where

a = (2^25-2^19-9)/3 = 11010045

b = [2^(a+27)-2^(a+2)-11]/3

c = [2^(a+b+29)-2^(b+2)-9]/3

d = [2^(a+b+c+31)-2^(c+2)-8]/3

and Mathew House on Discord reported that this makes the sigma value for this TM > (10 ↑)^4 6.5

--
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/b7b21c2c-973a-4baa-8318-3f5c4b804351n%40googlegroups.com.

[Daniel Yuan]

Thanks for the summary! I probably wouldn't have done as well. And it covers everything I wanted to say.

[Pascal Michel]

Let M be the 2x5 TM found by Daniel Yuan in June 2024, with s(M) > 10^(10^(10^3314360)).

Here, I give a proof that s(M) is approximately 3/2 (sigma(M)^2).

(1) Time for

 - Counter rules:

01 (11)^x <A (23)^y 00 --( 4(x + y) + 6 )--> 11 (01)^x <A (23)^y 21

01 (11)çx <A (23)^y 21 --( 4(x + y) + 6 )--> 11 (01)^x <A (23)^y 22

01 (11)^x <A (23)^y 22 --( 4(x + y) = 6 )--> 11 (01)^x <A (23)^y 23

so we have

. . .  <A (23)^y 00 --( . . . + 12y + . . . )-->  . . . <A (23)^(y + 1)

 - Overflow rules:

0 (11)^(x + 2) <A (23)^(y + 2) 0^3 --( 4x + 8y + 53 )--> 11 (01)^x 11 (01)^y  01 <A 21

0 (11)^(x + 2) <A (23)^(y + 2) 21 0^3 --( 4x + 8y + 73 )--> 11 (01)^x 11 (01)^y 11 (01)^3 <A 21

0 (11)^(x + 1) <A (23)^(y + 1) 22 0 --( 4(x + y) + 15 )--> 11 (01)^x (11)^(y + 2) 1 Z>1

(2) The time taken on the binary counter  is linear in the number of binary steps, so it is dominated by the time taken on the 23s, which is quadratic.

(3) The total time is dominated by the time taken from the 4th overflow to the last overflow.

Just before the last overflow, the configuration is

 . . . <A (23)^d 22 0^inf

So the total tome is

 T ~= (12x1) + (12x2) + . . . +(12x(d - 1)) = 12(d - 1)d/2 ~= 6 d^2

We have sigma(M) ~= 2d, so s(M) ~= 3/2 (sigma(M)^2).

[Pascal Michel]

(1) Erratum: the first overflow rule should be

0 (11)^(x + 2) <A (23)^(y + 2) 0^3 --( 4x + 8y + 53 )--> 11 (01)^x 11 (01)^y (11)^2 01 <A 21

(2) The TM enters the counter rules as soon as step 223:

0^8 <A 0^8 --( 222 )--> 11 01 01 11 01 11 12 <B,

which has the same future as 11 01 01 11 01 11 11 <A

At step 236, we get a configuration belonging to a counter rule.