19 views

Skip to first unread message

Mar 16, 2022, 2:17:56 AM3/16/22

to nichol...@gmail.com, Busy Beaver Discuss

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

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu