11 views

Skip to first unread message

Feb 22, 2022, 12:58:25 PMFeb 22

to Busy Beaver Discuss

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

Feb 27, 2022, 1:38:39 PMFeb 27

to Busy Beaver Discuss

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu