BBB(3, 3) > 10^62

[Shawn Ligocki]

I've completed my preliminary search of the 3x3 (3-state, 3-symbol) Beeping Busy Beaver space and can report the largest machine I found quasihalted at step 724193411946051617510910916281388064798340875589283913992444770 (> 7.2 * 10^62):

       +-----+-----+-----+

       |  0  |  1  |  2  |

   +---+-----+-----+-----+

   | A | 1RB | 0LB | 1LA |

   +---+-----+-----+-----+

   | B | 2LC | 2LB | 2LB |

   +---+-----+-----+-----+

   | C | 2RC | 2RA | 0LC |

   +---+-----+-----+-----+

1RB 0LB 1LA  2LC 2LB 2LB  2RC 2RA 0LC

Not quite as exciting as the huge 5x2 result, but it does have a bit of a handicap vs. that machine because the 3x3 case only has 9 transitions available to play with (vs 10 for the 5x2 case).

This was simulating all machines out to 100k loops (and most were discovered by about 2k loops). I don't think I'll find any more without some more clever searching.

My top 20 machines are:

1RB 0LB 1LA  2LC 2LB 2LB  2RC 2RA 0LC | None Infinite Chain_Move 1 724193411946051617510910916281388064798340875589283913992444770

1RB 2RA 0RB  2LA 0RA 1RC  1LC 0RC 0LA | None Infinite Chain_Move 1 220354559558397682030213400016811415718372

1RB 2RA 0RB  2LA 1RA 1RC  1LC 0RC 0LA | None Infinite Chain_Move 1 15580980266402105842515334512022435

1RB 0LB 1LA  2LC 0LB 2LB  2RC 2RA 0LC | None Infinite Chain_Move 1 390080064462054265224609560

1RB 0LB 1LA  2LC 0LA 2LB  2RC 2RA 0LC | None Infinite Chain_Move 1 390080064462054265224609560

1RB 2LC 2RA  1LA 2LB 1RC  1RA 2LC 1RB | None Infinite Chain_Move 2 2513054429677251202664472

1RB 2RA 1LC  2LB 0RB 2LA  1LA 0LB 1LA | None Infinite Chain_Move 2 71077530124878619721497

1RB 2RA 1LC  2LB 0RB 2LA  2RB 0LB 1LA | None Infinite Chain_Move 2 71077530124878619721453

1RB 0LB 1RA  2LA 0LC 0LB  2RC 0LA 1LC | None Infinite Chain_Move 1 15197724529812314937827

1RB 2LB 2RA  2LA 0RA 2LC  2LC 1LA 1RC | None Infinite Chain_Move 1 10198797959098448174

1RB 1LC 0LC  0RC 2RB 2RA  2LC 1LA 1RC | None Infinite Chain_Move 0 7517868007141161746

1RB 2LA 1LB  2LB 1LA 1RC  1RC 0LC 2RA | None Infinite Chain_Move 1 6527453367562341857

1RB 2LA 1RA  1RC 2RB 2RC  1LA 1LB 1LC | None Infinite Repeat_in_Place 0 549848197495100054

1RB 2RC 1LA  2LA 1RB 2LB  2RB 2RA 1LC | None Infinite Repeat_in_Place 0 4345166524812487

1RB 2RC 1LA  2LA 1RB 0RB  2RB 2RA 1LC | None Infinite Chain_Move 2 4345166429288408

1RB 1RC 0RC  1RC 0LA 1LB  2LC 2RA 1LB | None Infinite Chain_Move 0 1764080867102354

1RB 1LA 1LC  0LB 2RB 1RC  1LA 1RC 1LB | None Infinite Chain_Move 2 157875906390478

1RB 0RC 1RA  2LB 2LC 0RA  0RB 2LA 0RC | None Infinite Chain_Move 2 148679429347917

1RB 2RA 0RB  2LB 1LC 0LA  1LA 2RA 2LA | None Infinite Chain_Move 0 60264015839908

1RB 0LB 0RB  2RC 0RA 1RB  2LC 1LB 0RC | None Infinite Chain_Move 1 46411119490336

[Shawn Ligocki]

And I have just published an analysis of this machine: https://www.sligocki.com/2022/02/27/bb-recurrence-relations.html which required me to brush up on how to get closed-form solutions to linear recurrence relations.

The analysis is a bit more complicated than for previous cases, but leads to the quite concise description:

Let: g(m) = 0^inf <C 0^6 1^m 0^inf

Then:

* g(2k+1) -> g(13 * 2^k - 4) in B(6, k) + 26 * 2^k + 20 steps

* g(2k) -> Quasihalt at time B(6, k-1) + 26 * 2^(k-1) - 8

where B(a, k) = 2/3 (a + 7)^2 (4^k - 1) - 13 (a + 7) (2^k - 1) + 20 k

And this TM goes g(1) -> g(9) -> g(204) -> QHalt. Only 3 iterations ... but since each iteration takes roughly 4^m steps, that last iteration runs for a *long* time.