New BBB search strategy

[Nicholas Drozd]

tl;dr: Restrict BBB searching to ZERO-REFLEXIVE programs.

All known BBB champions exhibit a simple behavior that I'll call
"spinning out": the machine reaches a blank cell to the left (or
right) of all the marks on the tape, and the zero-instruction of its
current state tells it to move left (or right) and remain in the same
state. It can also be described as Lin recurrence with a period of 1.
This is the simplest behavior that a non-halting program can have, and
it's easy to detect. Any TM simulator can easily be modified to halt
upon spinning out.

Now, our knowledge of long-running programs is subject to a selection
bias of unknown severity. The best simulator available is designed to
search for Collatz-like behavior, and that's what it finds. One way to
respond to this is to develop new theories to describe and detect
other kinds of behaviors. But that's difficult. An alternative way to
deal with selection bias is to LEAN INTO IT. If we can only look for a
few specific behaviors, why not set ourselves up to look for those few
specific behaviors as effectively as possible?

Spin-outs are the easiest thing to detect and they seem to do pretty
well in the BBB game, so let's just focus on those. Call a program
ZERO-REFLEXIVE if it has any state that transitions to itself on its
zero-instruction. Then simply restrict searching to zero-reflexive
programs. Don't even bother searching the rest, since by definition
they can only exhibit behaviors that are harder to detect than
spinning out. This is analogous in the BB search to ignoring programs
without any halt instructions. Halt-free programs obviously cannot
halt, and non-zero-reflexive programs obviously cannot spin out. (This
approach belongs to STATIC ANALYSIS.)

Really this is a suggestion to Shawn to take another crack at BBB(5)
with this smaller search space. In conjunction with some tweaks to
simulator performance, I think greater champions are still available.
In fact, I will advance a WILD CONJECTURE:

* BBB(5) > BB(6)

We know that BBB(n) > BB(n + 1) for some n, and we know that these
things grow faster than we expect, so I think this is definitely true.
I even think it might be possible to find a witness to that, beating
the reigning BB(6) champ's 10^18267 steps.

Nick

[Shawn Ligocki]

Hm, very interesting idea Nick! I did a quick search and:

• 3x2 machines which are Zero-Recursive: 5_652 / 16_549 = 34%
• 4x2 machines: 1_014_696 / 2_943_669 = 34%
• 5x2 machines: 35% (sampled)
• 4x2 quasihalting machines: 470_046 / 950_730 = 49%

These numbers are actually pretty shockingly consistent for me! I would have expected them to change a bit from domain to domain, but it looks like among the 2 symbol results 34% are Zero-Recursive. And it also does look like we are a bit more likely to classify ZR machines as quasihalting, although there are still a number of non-ZR machines that make the top lists. Ex: 3/10 of the top BBB(4,2) machines are non-ZR. Specifically, these machines:

1RB 1RD  1RC 0LD  1LB 0RA  1LC 0LC | None Infinite Chain_Move 1 2332

1RB 0LC  1RC 1LD  1RD 0RB  0LB 1LA | None Infinite Chain_Move 2 1459

1RB 0RB  1LC 0LC  1RA 0LD  1LB 0LB | None Infinite Chain_Move 3 976

All 3 of these are Lin Recurrent with period 3.

Similarly, 7/20 of the top BBB(5,2) machines are also non-ZR. Specificially:

1RB 1LE  0RC 1LD  1RD 0RD  1RE 1RC  0LA 1LB | None Infinite Chain_Move 0 42988549223123458223625526105469064952566080280

1RB 1RA  1LC 0RB  1LE 0LD  1RA 1RE  1LB 0RA | None Infinite Chain_Move 3 12250514892052335897890345119247

1RB 1RC  1LC 0LC  1LD 1LB  0RE 1RA  1LC 1RD | None Infinite Chain_Move 4 3819473759206151487501440760838

1RB 1RD  1LC 1LB  1LD 1RA  0RE 0RD  1LB 1RE | None Infinite Proof_System 0 94418964659944351442398224758

1RB 0LB  1RC 0RC  0RD 1LA  1LE 1RD  0LC 0RE | None Infinite Chain_Move 1 709060927863744259444952305

1RB 0RB  0RC 1LE  1LD 1RC  0LB 0RD  1RA 0LA | None Infinite Chain_Move 0 709060927863744259444952303

1RB 1LC  0RC 0RB  1LD 0RE  0RA 0LA  1LB 1RE | None Infinite Chain_Move 1 28671636865949167174294799

Which have quasihalting behavior:

1. 0 <D 1 -(3)-> <D 11
2. 000 <C -(3)-> <C 111
3. 1 C> 0 -(3)-> 11 C>
4. (As previously discussed, this one is not even Lin Recurrent at all)
5. 0 <C 0 -(3)-> <C 01
6. 0 <B 0 -(3)-> <B 01
7. 0 <D 1 -(3)-> <D 11

So, of the top machines that are not ZR, almost all appear to be LR-3, for what that's worth.

-Shawn

--
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/CABAiW0o%3DdYu3iig80C41wjKF%3D3eqUQ3ky0RjKQqctEf2R9zYOg%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Nicholas Drozd]

Yes, this approach has a provably catastrophic false negative rate
with respect to the actual BBB function. But remember, we are
embracing our limitations here.

In fact, define the Spinning Beaver sequence SB to be like BB except
that instead of halting the termination condition is spinning out. It
is overwhelmingly likely that SB > BB, but they are still
equicomputable, just like BLB. But unlike BLB, BBB(n) >= SB(n) for all
n by definition. So any new SB result is a new BBB result, and what
I'm proposing is that it might be feasible to find one.

What we get in exchange for limiting our ambitions is improved static
analysis. Behaviors like Lin recurrence and Ligocki recurrence (???)
are examples of what Marxen calls FORWARD REASONING. They are
available for BBB searching just as they are for BB. BB can also be
searched with BACKWARD REASONING. Because there is a specific
instruction that must be reached, it is possible to prove in some
cases that this cannot be done, and that the machine will never halt.

Spinning out is a pretty specific circumstance, and so this can be
done for SB as well. Consider:

--> 1RB 0LA 1LB 0RC 1LA 1RC

I claim that this zero-reflexive program will not spin out. It has
just one zero-reflexive instruction: B0 -> 1LB. To spin out, the
machine needs to be scanning a blank with no marks to its left. But
the only way to reach B is from A, which always prints a 1 and moves
right before going to B. So B0 can never be reached without marks to
the left.

A program can have multiple ZR instructions, and in general this needs
to be verified for all of them. But otherwise it's not so different
from checking for non-halting.

This is an additional step of reducing the holdout list after purging
everything that isn't ZR. Of course there's no way of knowing how
impactful it will be, and it will definitely become less effective as
the number of states increases. But 5x2 seems small enough that it
could reduce the list significantly.

[Shawn Ligocki]

Agreed, this is very interesting. FWIW, I have started using the name "Chain Recurrence" for this behavior (Lin Recurrence of period 1) since (for some reason I don't remember) we call it a Chain Step when you have tape compression and move across a whole block of 1 symbol. I like the whimsicality of "Spinning Beaver", but it feels a little misleading, since it is actually characterized by never again changing direction, a bit the opposite of spinning :) Perhaps if you want to keep the SB acronym you could call them Sprinting Beavers?

I agree completely that SB is a very interesting space between BB and BBB in a way that is clearer to state than BLB and BLR and it's great to see that we could apply "backwards reasoning" again here! In fact, SB seems to be roughly the aspect of BBB that we are most equipped to search for starting from the BB code.

I'm not sure what you are referring to as Ligocki recurrence, but I can assure you, none of this is our invention. If it's the proof system rules, I learned those from Heiner Marxen (I think he calls them "pure additive configuration transitions" (PA-CTRs) ... although PA-CTR Recurrence is a bit of a mouthful!).

--
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/CABAiW0qnVMC1m8FXNHuHD0f_SuAvP%2BYBJbDz6NnV%3DT3Nqb%2BBxg%40mail.gmail.com.

[Nicholas Drozd]

I implemented a basic spin-out backwards reasoning check. It's a
little tricky, and there's more to do, but it works. In fact, I
believe that SB(3, 2) can be declared fully, no-hand-waving solved!

As for the name, there are a couple of reasons I think "spinning out" is good:

1. Getting stuck in one state moving one direction forever is a
degenerate behavior, and the name should evoke that. When this
behavior is detected, it is clear that although the machine might
still be running in some sense, the computation is unmistakably
finished. The image that always comes back to me is a turntable
reaching the end of a record. It will keep spinning forever, but
there's no more record to play.

2. Imagine a physically implemented Turing machine with the tape
spooled up on actual reels. A spin-out program run on such a device
really would cause the reels to spin out! (See
https://www.youtube.com/watch?v=E3keLeMwfHY)

As for "chain recurrence", IIUC that's a more general kind of action.
It doesn't just apply to the edge block, it applies to skipping any
block.

In your post you say: "Chain Recurrence is the easiest way to detect
quasihalting. All you need is a simulator that has Tape Compression
and performs Chain Steps." But in fact tape compression isn't required
to check for this behavior. A fully naive simulator with no tape
compression can be modified to check for spinning out.

The only conditions that need to be checked are: the current cell is
blank, and all cells to the left (or right) are blank, and the next
shift is left (or right), and the next state is the current state. And
these conditions can all be checked regardless of how the tape is
represented.

[Nicholas Drozd]

Here's a question: if we assume that the machine's first shift is to
the right, will an SB champion spin out to the left or to the right?

There shouldn't be a general pattern. If there were, it could be used
to improve search. Say the answer was that they always go to the left.
Then we could just ignore any machines without left zero-reflexive
instructions. But that feels too good to be true.

Among known champions, 3x3 moves to the right and all the rest move to the left.

[Shawn Ligocki]

On Mon, Feb 28, 2022 at 10:13 AM Nicholas Drozd <nichol...@gmail.com> wrote:

I implemented a basic spin-out backwards reasoning check. It's a
little tricky, and there's more to do, but it works. In fact, I
believe that SB(3, 2) can be declared fully, no-hand-waving solved!

Exciting news! It's always great to have a definitive statement :)

As for the name, there are a couple of reasons I think "spinning out" is good:

1. Getting stuck in one state moving one direction forever is a
degenerate behavior, and the name should evoke that. When this
behavior is detected, it is clear that although the machine might
still be running in some sense, the computation is unmistakably
finished. The image that always comes back to me is a turntable
reaching the end of a record. It will keep spinning forever, but
there's no more record to play.

 

2. Imagine a physically implemented Turing machine with the tape
spooled up on actual reels. A spin-out program run on such a device
really would cause the reels to spin out! (See
https://www.youtube.com/watch?v=E3keLeMwfHY)

Thanks, I like the analogies. I don't want to spill too much ink here bikeshedding, but I will list one more reason that I am not completely on board with this name. There are many ways in which a TM could have "degenerate" behavior. This is the first one we're focussing on (because it is especially simple and widespread), but over time, I imagine more will be identified and talked about. When I hear spin-out, I mostly hear it as a synonym for degenerate behavior, so my worry is that we end up in a future where a machine could "spin out" or "lose it's mind" or "go sisyphus", etc. with each of these having some technical definition, but for the uninitiated, they all sound like synonyms and so would cause confusion and frustration. For that sort of reason, I'm always in favor of names that are more descriptive of the specific behavior we're seeing (say, sprinting because no TM can run faster than these machines). OK, I'm done :)

As for "chain recurrence", IIUC that's a more general kind of action.
It doesn't just apply to the edge block, it applies to skipping any
block.

Here I am attempting to distinguish two terms: a "Chain Step" is a general action that can applied to any block of symbols and "Chain Recurrence" is the "operating state" a TM enters after applying a Chain Step to an infinite block. In general, I have started using "Recurrence" exclusively to describe infinite recurrence, i.e. a behavior that once you start you repeat forever. I could see that you could also think of a Chain Step (or a Rule Step as well) of being an application of what you might call bounded recurrence. I have been avoiding using the word recurrence for bounded repetition.

In your post you say: "Chain Recurrence is the easiest way to detect
quasihalting. All you need is a simulator that has Tape Compression
and performs Chain Steps." But in fact tape compression isn't required
to check for this behavior. A fully naive simulator with no tape
compression can be modified to check for spinning out.

That's true. I suppose what I meant by this is that if you have implemented Tape Compression and Chain Steps, you basically have no choice but to implement Chain Recurrence detection ... it's sort of built into the algorithm (unless you explicitly make a special case to only apply base steps to the 0 blocks or something like that). But I agree, even with an uncompressed tape, it requires only a medium-small modification to detect CR. But also, once you've spelled out the correct specification for CR detection, you're 90% of the way to implementing Chain Steps more generally, so you might as well do tape compression, right?

[Nicholas Drozd]

I think we can agree that there is room to workshop the terminology
further at some point. Maybe we could convene a focus group! I'm only
half-joking; we're definitely dealing with something that's worth
communicating, and doing that the right way is important.

Earlier I said "BBB(n) >= SB(n) for all n by definition". In fact this
is not true. Consider the BLB(3, 2) champion:

--> 1RB 1LB 1LA 1LC 1RC 0LC

It spins out (on the blank tape) after 34 steps, demonstrating that
SB(3, 2) >= 34. But it quasihalts after just 6 steps. For another
example, there is the BLB(2, 4) champ:

--> 1RB 2RA 1RA 2RB 2LB 3LA 0RB 0RA

This one spins out (on the blank tape) after 1,367,361,263,049 steps,
but it quasihalts 7 million or so steps before that.

Quasihalting remains a slippery predicate, so we have to be careful
about what exactly can be proved.

That said, I do still believe that searching for SB will yield BBB
results, and that SB(5, 2) > BB(6, 2).

[Shawn Ligocki]

Ah, good catch Nick, these definitions are so very twiddly to reason about! I think we can confidently say that any TM which "Spins out" has already Quasihalted, but as you mentioned, the quasihalt time may be much earlier than the spin-out time. Likewise I think we can confidently say that "SB(n) <= BBLR(n)" since SB is just Lin Recurrence restricted to periods of length 1 (and they both have the same "halt condition").

After spending some time searching for Beeping BBs, I've noticed this sort of issue that you brought up. Specifically, that we are generally proving Quasihalting by observing that a TM has gone through a "phase transition" from an initial complex behavior to a simpler degenerate behavior. We then think about these phase transitions and can give them names (Spinning out, Lin Recurrence, etc.) and can consider the BB-like functions connected to them (SB, BBLR, BLB, ...). But then to actually decide if this machine quasihalted and if so at what time requires analyzing the list of states used in the recurrence (is any state missing from this list) and keeping track of the last time each of those states was seen. I'm left feeling like we are ignoring some very interesting machines which exhibit complex phase transitions, simply because after that transition, they continue to touch all states in each recurrence and so they do not qualify for BBB.

In a way, it feels that what we are really doing right now is searching for SB, BBLR, etc. and that incidentally, this has allowed us to find the best BBB. I suppose that's what you've been saying in these messages, that it might make sense (at first) to set our sights on SB and take advantage of some optimizations that this allows (restricting to Zero-Reflexive TMs, etc.).

[Shawn Ligocki]

I just saw this email. This is interesting, it looks like there might be some sort of bias here between SB direction relative to start direction (although this sample size is pretty small :) ).

I've developed an intuition around this sort of thing by imagining TM behavior as sort of stochastic (i.e. random) in that, say, there is a certain chance that a TM will simulate Collatz-like behavior and then given that, it will simulate a random specific Collatz-like function, and then given that, it will simulate starting at a random initial parameter. And even for Collatz-like functions, my intuition is that the orbit lengths will be distributed roughly the same as if we rolled a die to decide the remainder at each step (rather than deterministically determining it). So then, when we look over all TMs, we find that many simulate all sorts of different Collatz-like functions and the ones that get the most "lucky" by finding the most productive Collatz-like functions and initial parameters. In other words, it feels to me like the reason that BB(6, 2) is so much greater than BB(5, 2) is that the total number of 6x2 TMs is so much larger and so they get to simulate many, many more Collatz-like functions and the "luckiest" TMs are expected to get even luckier than their 5x2 siblings (who had many fewer chances to win the lottery). This is in contrast to the idea that BB(6, 2) is much greater than BB(5, 2) because the 2 extra transitions give it more "power" in some traditional sense (like allowing it to implement some new technique).

This is a long way of saying that, using this style of intuition, I might guess that at any moment during computation there's some "chance" that each TM will eventually spin out in either direction and maybe the initial instruction's move direction is locked down to R, that leads to the chance being 3x higher to for L than for R? So I don't think we could "depend" upon it to find SB champs, but maybe there are still heuristics that could guide our search if we don't have enough compute power to enumerate everything to get more "bang for our buck".