BBB(5, 2) > 10^14,006

[Shawn Ligocki]

I have another pair of prolific machines for all you Busy Beaver hunters:

1RB 1LE  0LC 0LB  0LD 1LC  1RD 1RA  0RC 0LA

1RB 1LE  0LC 0LB  0LD 1LC  1RD 1RA  0LD 0LA

which each run for over 10^14006 steps before quasihalting!

Like all previous champions, they quasihalt by "Spinning Out". In this case, they blank the tape in state D, the only Zero-Reflexive state.

These each take 12 seconds and 498,191 simulator "steps" using our accelerated simulator. I was actually pretty lucky, I was only running to a max of 500k simulator steps!

[Shawn Ligocki]

This machine turned out to be quite easy to analyze because it's behavior is extremely similar to the last two machines Nick found. Specifically, this collatz analysis applies to both machines:

let

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

then:

• G(4k  , m+2) -> G(7k+ 7, m)
• G(4k+1, m+2) -> G(7k+ 8, m+1)
• G(4k+2, m+2) -> G(7k+ 8, m+1)
• G(4k+3, m+2) -> G(7k+14, m)
• G(n, 1) -> G(1, n+3)
• G(n, 0) -> Spin Out
  

If you compare this to my Collatz-like analysis of the 10^4079 machine (emailed on Mar 16), you'll see that it is extremely similar! The only difference is two of the constants on the right have changed. And likewise the 10^325 machine also had a similar Collatz-like analysis. So it appears that the 5x2 TM space has been able to simulate many parameterizations of these 2-stage style Collatz-like functions and we are noticing the especially "lucky" ones which run for quite a long time before quasihalting (but not toooo "lucky" or else my simulator will not run long enough to catch them).

The orbit for this TM starting on a blank tape is:

0 : G(1, 1)

1 : G(1, 4)

2 : G(8, 3)

3 : G(21, 1)

4 : G(1, 24)

5 : G(8, 23)

6 : G(21, 21)

7 : G(43, 20)

8 : G(84, 18)

9 : G(154, 16)

10 : G(274, 15)

11 : G(484, 14)

12 : G(854, 12)

13 : G(1499, 11)

14 : G(2632, 9)

15 : G(4613, 7)

16 : G(8079, 6)

17 : G(14147, 4)

18 : G(24766, 2)

19 : G(43345, 1)

20 : G(1, 43348)

21 : G(8, 43347)

22 : G(21, 43345)

...

28_832 : G(2533...2210, 0)

Spin out

So, it grew m up to >43k before spinning out (vs. 12k in the 10^4079 case).

I am feeling more an more confident in predicting that SB(5, 2) > 10^10^10 and even probably SB(5, 2) > 10^10^10^10 although I'm worried that if we find a machine demonstrating that higher bound, we won't be able to prove it does with existing theory! :/

[Nicholas Drozd]

Great finds! Are you searching over your whole generated list of programs or have you filtered down to just the zero-reflexive programs?

It's interesting that these two and the 10^4079 step program are all almost identical. In fact the 10^4079 one and the second that you have listed here even have the same control flow graph.

We might guess that it shouldn't be possible to make minor tweaks to the true champion program and still get another high scorer. From that perspective, this clustering of successful programs is evidence that the true champion is yet to be found (for BBB certainly, but also SB and BLB).

On the other hand, it might be worth exploring further minor variations of these programs. After all, if a few of them are high-scoring, why shouldn't there be more?

[Shawn Ligocki]

Nick, great minds think alike, let me introduce you to the "Mother of Giants"

|     |  0  |  1  |

| :-: | :-: | :-: |

|  A  | 1RB | 1LE |

|  B  | 0LC | 0LB |

|  C  | 0LD | 1LC |

|  D  | 1RD | 1RA |

|  E  | ??? | 0LA |

all three pre-existing champion machines are "children" of this machine (by defining the E0 transition) and 5 of the other children appear to be even more prolific: https://www.sligocki.com/2022/04/03/mother-of-giants.html

And we are now in a strange situation: I believe these 5 siblings will beat our existing champions ... but have no idea how to show it :(

[Nicholas Drozd]

We're in deep territory here!

The child with E0 -> 1RD shows up as quasihalting after 10^12,978 steps. This is "a little" less than the other two, but it takes longer to work out: 520,761 loops. In full:

  * 1RB 1LE  0LC 0LB  0LD 1LC  1RD 1RA  1RD 0LA

By the way, of the two machines you posted, which one actually runs longer? They're close enough that it's not trivial to distinguish the two numbers!

[Shawn Ligocki]

You're right Nick, 1RD does quasihalt within a reasonable number of steps (I'd made a mistake in my analysis earlier, I've updated the Blog post with this correction)!

To answer your questions:

• 0RC runs slightly longer than 0LD by making a slight (2 step) detour every time it reaches the E0 transition.
• I am searching over all 10M 5x2 unknown TMs (not filtering to ZR machines).
• The runs are still ongoing (~75% complete with 500k simulator steps).

In the past I have never noticed a situation in which slight modifications to a champion produced anything interesting ... but I am not convinced that is evidence that none of these will be the Spinning Beaver. It seems that this Mother of Giants has discovered a general mechanism for simulating extremely long running TMs (which all "probviously" halt). Since each of her children tweak the Collatz model slightly, it allows them to search the "Collatz space" for the most prolific iterations. This seems to me (now, in hindsight) like a great strategy for producing the most prolific TM. In some ways this could be even more evidence against the SCC. This Mother of Giants is another sort of structure (where we categorize a whole group of machines into a high-level behavior, with each child adding a small tweak onto the higher-up structure).

That said, I don't think we're anywhere near done in our search! If anything, I found these machines exactly because they have siblings like themselves. If it wasn't for these 4 "large" siblings (0RC, 0LD, 1RD and 0RD) which my simulator can run in ~10 seconds or less, I never would have seen the "giant" siblings (1RC, 1LC, 1LA, 0LC) which my simulator has no hope of running to completion. So, for sure, there is a huge selection bias here again :)

[Shawn Ligocki]

I have found more Giants, this time they are perhaps "cousins". I've renamed

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

a slight change, but the analysis is very similar.

• 1RB 1LE  0LC 0LB  1RD 1LC  1RD 1RA  0RC 0LA
  

• 1RB 1LE  0LC 0LB  1RD 1LC  1RD 1RA  1RD 0LA

These both calculate the same Collatz-like function and reach G(10^146_129.8, 1) at which point I cannot simulate them any more.

• 1RB 1LE  0LC 0LB  1RD 1LC  1RD 1RA  1LB 0LA

Reaches G(10^49.1, 1)

• 1RB 1LE  0LC 0LB  1RD 1LC  1RD 1RA  1LA 0LA

Reaches G(30_529_268_418_513_771_980, 1)

• 1RB 1LE  0LC 0LB  1RD 1LC  1RD 1RA  0LB 0LA

Reaches G(11_296_438_824_937_057, 1)

So we have a growing family here of "probviously" long-running machines. Perhaps there are more cousins as well? I only looked in one lineage (C0->???)

[Nicholas Drozd]

> I would be shocked to discover that they somehow manage to dance perfectly into the reset lane every time!

There are two ways of looking at this.

The first way is how you've laid it out. It seems like these sequences can't keep going on forever, because that seems way too lucky. It would be as if there were some number-theoretic forces conspiring to keep m from ever reaching 0. But as far as we can tell these things behave more or less randomly, and so surely the iterations will eventually work out such that m reaches 0 and it terminates.

But this randomness argument can be turned around. To say that these functions always terminate is to say that they are effective procedures. It's to say: you can give me any number you want, and I can run it through this weird mod-4 procedure and give you back some output. But why should an apparently random procedure always terminate? We do this 4 -> 7 transformation, throw in a 14 here and an 8 there and ... profit??? Why should we expect that to always work?

Is there any sense in which we can say that a "randomly" chosen Collatz-like function ought to terminate or not? Is termination or non-termination the default assumption?

If I had a rigorous argument one way or another, I'd be pretty clever! Instead, we're stuck in the unfortunate circumstance of having these two perspectives that each seem plausible but are diametrically opposed.

[Shawn Ligocki]

But this randomness argument can be turned around. To say that these functions always terminate is to say that they are effective procedures.

Could you help me understand what you mean by "effective procedures". I read the Wikipedia article, but I'm not sure I understood it. Are you saying something like: This type of Two-stage Collatz-like function might be Turing complete and if it is then the halting problem is undecidable for them which means that some will never halt? I'm not convinced that two-stage Collatz-like functions are Turing complete ... but I don't know how to prove it either :)

 

It's to say: you can give me any number you want, and I can run it through this weird mod-4 procedure and give you back some output. But why should an apparently random procedure always terminate? We do this 4 -> 7 transformation, throw in a 14 here and an 8 there and ... profit??? Why should we expect that to always work?

Or maybe you are saying that many of these parameterizations (maybe most) will lead to halting process, but it would be foolish to say that of all the parameterizations, none run forever?

 

Is there any sense in which we can say that a "randomly" chosen Collatz-like function ought to terminate or not? Is termination or non-termination the default assumption?

I don't think either is default in general. It depends on the behavior. My intuition is telling me that I should think of Collatz-like functions like random functions (with some caveats). If the random version of the function halts 100% of the time, then I claim the Collatz-like version "probviously" does too :) If the random version halts 50% of the time, then maybe I'd guess that half of parameterizations/starting values will lead to halts and half not, etc. Is this intuition accurate ... probably not, but it's definitely my Baysian prior. And furthermore, I wouldn't be too surprised if one or two cases contradict this intuition, but we now have 7 completely different parameterizations. What's the chance that they all run forever :)

[Nicholas Drozd]

I've been thinking a lot about the Collatz conjecture (a dangerous pastime, I know). There are still lots of details to work out, so I'll do my best to clarify it.

When I say "effective procedure", I just mean a method of calculation that is guaranteed to return an answer. For example, there is an effective procedure for determining if a number is even or odd. You can pass in any number you want, and you are guaranteed to (eventually) get an answer. Outside of things like Turing machine simulators, most code we write deals with effective procedures.

Given a Collatz-like function F, is F effective in this sense? Or is there some input n such that F(n) doesn't terminate? That's what we want to know. Really, we're asking an even easier question: for a certain particular argument a, does F(a) terminate? (Specifically, do these various children of the MoG terminate for their particular starting arguments?)

If it does terminate, that's provable, at least in principle. It's "just" a matter of feasibility. If it doesn't terminate, what then? Nobody knows how to prove that, and nobody knows if it's provable at all.

So we're stuck trying to distinguish between the case where it does terminate but we can't run it long enough to find out, and the case where it doesn't terminate. Again, this is just for a single function and a single input.

Now your feeling, at least as I understand it, is that we should assume that the particular functions at hand do terminate on these particular arguments, because it would be strange for the m value to somehow hit the reset lane over and over and over forever. If you think about each iteration as a dice roll, then it would seem to require an infinite amount of "luck" to avoid ever terminating.

Like I said, this sounds plausible enough to me, and I certainly have no proof against it. But you could also look at it from a more skeptical perspective. Suppose we look at termination of the function as success and non-termination as failure. Now imagine someone comes to you with some Collatz-like function they wrote by hand, with a bunch of unexplained and seemingly arbitrary constants (7, 15, etc). They claim to you that the function definitely always terminates. Should you believe them? Isn't it possible that they've messed up and the function actually doesn't terminate for some input?

From a function design perspective, how hard is it to terminate? How hard is it to not terminate? Which one is the bullseye?

[Nicholas Drozd]

Here's one more that spins out after 10^12978 steps:

 * 1RB 1LE  0LC 0LB  0LE 1LC  1RD 1RA  1RD 0LA

This one differs from the other 12978 not at the E0 instruction, but rather at the C0 instruction. So it's another "cousin".

Their runtimes differ by exactly one step.

[Shawn Ligocki]

Nice find, Nick. The only other "sibling" (differing only in the E0 transition) I have of this machine (that has not been categorized) is:

* 1RB 1LE  0LC 0LB  0LE 1LC  1RD 1RA  0LD 0LA

This one is interesting because it's the first example among these I've seen where I can prove that it will never Quasihalt! Specifically, it satisfies the following Collatz-like relation:

let GD(n, m) = 0^inf <D 0^n 1^m 0^inf

then:

• GD(4k+1, m+2) -> GD(8k+10, m+1)
• GD(4k+2, m+2) -> GD(8k+ 9, m+1)
• GD(n, 1) -> GD(2, n+3)
  
• Blank -> GD(2, 1)

Thus:

• Since 8k + 10 = 2 (mod 4) and 8k+9 = 1 (mod 4) we never touch the GD(4k+0, m) or GD(4k+3, m) configurations.
• Since both rules which reduce m only reduce it by 1, we will never touch the GD(n, 0) configuration.
• So this machine will never Quasihalt (it will reset every time it reaches stage 2).

--
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/CABAiW0rb%3D22x2ixNqYrBc6iX%2B%3DMvPaBs-4%2B4BjurcjRpnXGCpg%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.