BBB 5x2 10^315

[Shawn Ligocki]

Nice find Nick!

In TNF, this machine is: 1RB 0LE  0LC 0LB  1RD 1LC  1RD 1RA  1RA 1LA

This machine actually has a very interesting (and reasonably concise) analysis:

let (This is my state C ... I think it would be your state D):

• G(n, m) = 0^inf <C 0^n 1^m 0^inf

then:

• G(4k  , m+2) -> G(6k+ 5, m)
  
• G(4k+1, m+3) -> G(6k+ 9, m)
• G(4k+2, m+3) -> G(6k+10, m)
• G(4k+3, m+2) -> G(6k+10, m)
  
• G(n, 1) -> G(0, n+3)
• G(n, 0) -> Chain Recur (Spin Out)

and (the TM never reaches these starting at a blank tape, but for completeness):

• G(4k+1, 2) -> G(6k+4, 1) -> G(0, 6k+7)
  
• G(4k+2, 2) -> G(6k+5, 1) -> G(0, 6k+8)

The TM reaches G(0, 1) at step 3. So the configurations are:

• G(0, 1)
• G(5, 1)
• G(0, 8)
• G(5, 6)
• G(15, 3)
• G(28, 1)
• G(0, 31)
• G(5, 29)
• G(15, 26)
• G(28, 24)
• G(47, 22)
• G(76, 20)
• G(119, 18)
• G(184, 16)
• G(281, 14)
• G(429, 11)
• G(651, 8)
• G(982, 6)
  
• G(1480, 3)
• G(2225, 1)
• G(0, 2228)
• G(5, 2226)
• G(15, 2223)
• G(28, 2221)
• G(47, 2219)
  
• ...
• G(136267537993817948712582092875398040791770763719698038991919564713488544469336292511701697868951401770001455377712171625806307626201921007174857828254368679680, 0)
• Spin out

I've grouped this in such a way to emphasize the "2-stage" aspect of this Collatz-like behavior. Specifically, we could say that stage 1 is iterating this basic Collatz-like function:

• h(4k  ) -> 6k+ 5
  
• h(4k+1) -> 6k+ 9
• h(4k+2) -> 6k+10
• h(4k+3) -> 6k+10

that function is iterated until m < 3 at which point stage 2 happens. In this case it's just a simple check

• if m == 0, Spin out
• otherwise, reset m to a number O(n) and n to 0 and go back to stage 1

This TM got "lucky" in that it iterated through stage 1, 4 times before finally spinning out.

How lucky was this? Actually, 15 / 100 of the combos (a, b) for 0 <= a, b < 10 iterate through stage 1 over 4 times. How many times do they iterate through stage 1 ... I do not know because at this point they become unsimulatable by me. Take for example this orbit:

• G(3, 1)
• G(0, 6)
• G(5, 4)
• G(15, 1)
• G(0, 18)
• G(5, 16)
• ...
• G(281, 1)
• G(0, 284)
• G(5, 282)
• ...
• G(6914454136514142346775, 1)
• G(0, 6914454136514142346778)
  
• G(5, 6914454136514142346776)
  
• ...

At this point we will need to run stage 1 here for > 10^21 iterations before we find out if it spins out or resets. I don't know any way to speed that up by more than a constant, so it will be hard to run this iteration to completion. (Even if you could iterate once per nanosecond, you would need >30k years to calculate!) [Of course, let me know if any of y'all know of an efficient way to accelerate this!]

And, in fact, this example is realizable by adding just 2 more states at the beginning of our TM. Say Start state X, X0 -> 1LY, Y0 -> 1LA which leaves us in:

• A0 11
• 1 B1 1
• B1 01
• B0 001
• C0 0001 = <C 0^3 1^1 = G(3, 1)

Rewriting this into TNF, we have the 7x2 TM:

• 1LB ---  1LC ---  1RD 0LG  0LE 0LD  1RF 1LE  1RF 1RC  1RC 1LC
  

which "probviously" spins out (and thus quasihalts) eventually ... but we cannot say when ... or even how to prove that it does eventually spin out!

Of course, these 2 added states are being used extremely inefficiently, so I'm sure there is a TM in 6x2 with behavior like this (and maybe even in 5x2?)

Great find Nick!

-Shawn

On Tue, Mar 15, 2022 at 2:48 PM nichol...@gmail.com <nichol...@gmail.com> wrote:

I found another high-scoring non-champion 5x2 quasihalter:

  --> 1RB 0LC  0LD 0LB  1RA 1LA  1RE 1LD  1RE 1RA

It quasihalts after 10^315 steps. Not quite 10^502, but still 3rd place in Shawn's 5x2-Beep-Top list.

--
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/a45d836e-8375-44e9-b2b7-a95ed8638eedn%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.