BBB(5, 2) > 10^4079

[Nicholas Drozd]

I am pleased to report a new Beeping Busy Beaver champion:

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

This 5x2 program quasihalts after 10^4079 (7467...5736) steps.

Wow!

I found this running the Ligocki simulator on a single modest desktop.

In his previous report, Shawn said that he generated almost 700
million 5x2 programs and that he ran them for 50,000 simulator loops.
Well, this champion takes 131,001 simulator loops. The trick here was
the aggressive pruning strategy discussed in the other thread,
resulting in a list of around 800,000 programs.

The situation is this. Quasihalting is an unbelievably general kind of
behavior, and that's why BBB is super-uncomputable. It's totally
unmanageable and way outside the bounds of what we can imagine. We
have to set our sights lower and focus just on those particular
instances of quasihalting that we can actually detect.

The simplest kind of quasihalting is what I've called SPINNING OUT.
This means that the machine is past the edge of all the marks on the
tape, and the next instruction says to move further past the edge and
stay in the same state. This is a very easy behavior to detect.

All known BBB champions spin out.

It's not a coincidence that the things we can detect are things that
are easy to detect. In fact it is a DEEPLY TROUBLING EPISTEMOLOGICAL
LIMITATION. We can only find what we can find.

It isn't all bad though. We can take advantage of this by focusing on
just the things we know can be found (and ignoring the things we know
are beyond our means).

For a program to spin out, it must have at least one ZERO-REFLEXIVE
instruction; that is, an instruction of the form X0 -> _ _ X. Programs
without zero-reflexive instructions can be scrapped, as they
definitely cannot spin out. This is a technique of STATIC ANALYSIS,
equivalent to ignoring halt-free programs in the classic Busy Beaver
setting.

Another technique from classic BB is BACKWARD REASONING. This is a
DYNAMIC ANALYSIS technique that entails running a program backwards
from its halt state to possibly show that the halt state cannot be
reached. This can be adapted to show that some programs cannot spin
out even if they do have zero-reflexive instructions.

These pruning methods so far are perfectly defensible. I also used one
more pruning method that is much more aggressive and speculative, and
this has to do with the GRAPH REDUCTION PROCEDURE discussed in the
other thread.

There is an idea called the Spaghetti Code Conjecture that says Busy
Beaver champions ought to be complicated "spaghetti code". In fact
there is no evidence for this conjecture; all known champions are
actually quite simple in terms of their control flow. Thus opposing
the SCC is the Clean Code Conjecture, which says that champions ought
to be simple. There is a graph-theoretic procedure that can be used to
make this idea rigorous, and I used it in pruning. Only graph-simple
programs were searched, and all others were scrapped.

(For more details, see:
https://nickdrozd.github.io/2022/03/12/formal-theory-of-spaghetti-code.html)

As I said, this is a more speculative step. I'm not sure how impactful
it was, as I didn't keep any stats at the program generation stage.

Anyway, this is a nice result, but I don't think it's the true champion.

*** PREDICTION (VERIFIABLE BUT NOT FALSIFIABLE) ***

I believe that BBB(5) can be shown to be greater than the best known
value of BB(6), namely 10^36534.

[Shawn Ligocki]

Wow, wow, wow! I actually ran all 5x2 TMs out to 100k simulator steps. But that didn't find anything new (and neither had any limits since 25k), so I gave up! This pruning strategy looks fruitful!

This machine actually behaves extremely similarly to the 10^325 champion you posted previously. Here is my analysis:

let

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

then

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

and for completeness (although we can never reach G(0, m) by applying these rules):

• G(0, m+2) -> G(7, m)

and finally, at step 4 we are in G(1, 1).

As before, iterating these relations leads to a sort of "2-stage" Collatz-like behavior:

• G(1, 1)
• G(1, 4)
• G(8, 3)
• G(19, 1)
• G(1, 22)
• G(8, 21)
• G(19, 19)
• G(42, 17)
• G(76, 16)
• G(138, 14)
• G(244, 13)
• G(432, 11)
• G(761, 9)
• G(1338, 8)
• G(2344, 7)
• G(4107, 5)
• G(7196, 3)
• G(12598, 1)
• G(1, 12601)
  
• G(8, 12600)
• G(19, 12598)
  
• ...
• G(1876213840710521598391379605525487806521622108810778432527722867392307436766159159315654305525834552560172561652032118063458627370309987185176524224005388698700446967268349729419384342385261686600728253800107702390205303703109911013679543376784994065131479319486732208008605302317371513424001996538578227420511014587912085639154043098929108973505716971259211164084851171147584492195641828442403195419357046301200977722765015982127629619366127227507539382553155352425623517192820793588314301840633848042122283284527197514334793445174332133304252240350530614310123013246222482691057522680607329801073658994807307108563977792602674937915145127717601763644562450026084468482011253492787037376937107425102889344711991496275353115166560777221320784075353693443765935139868061950972649919070516499077698769361018135243624369764825602272332642411663431603264357025025605181511270774475664657506683051463739351416893336641567178700404415824985611548629898352736718482963400988142981278524634899806152389037871669098549259903261356156435822856442997107359268004720245053216395652317114834047445010107196444627059271727548915696497640596592913994488623239627564677236759609661035594688933526335837056500047460869283130575904150442715133699885285716657627307991036082003072952095275483832305837708309180971389464320818551264951669392266140549796563778468321806984538951296296552524443477377012382914243026356951988052699080778947387243967930857325467739175240274180541636551276654811833607927610176824006302410755537315645723335878886137585589884378754363497710819886157044977428594424751379562193743624891055837449756993817095474523342307530343858042369299814007843193782820421402610428397007107529266963233646286254595510683332294534735691214261351756352969840115522216379692717569241523917906031879093475856928361266209321993314289669996574460021380115709710519270157850694498748462253621222466800698577194648206832226152375452456786050873778773714111576650409478390819793529657854689649591879416169292957147115001498762307255727596635383777744252057, 0)
  
• Spin Out

This TM has 2 main improvements over the one I analyzed yesterday:

1. Yesterday's iterated 4k -> 6k in stage 1. Today's iterates 4k -> 7k in stage 1. This is a modest improvement.
2. Yesterday's reduced m by 2 or 3 each iteration of stage 1. Today's reduces it by 1 or 2 each iteration. This is a huge improvement! It allows stage 1 to run almost 2x as long for the same starting value of m!
• Ex: Yesterday's: G(0, 31) -(13)-> G(2225, 1).   [-(13)-> means in 13 iterations]
• Today's: G(1, 22) -(13)-> G(12598, 1).   [So it was able to iterate 13 times as well even though it started at a smaller m value: 22. And thanks to (1) 13 iterations led to a much larger value for n.]

The behavior of these two machines is really shockingly similar (and I can see that the transition tables are also very similar). This is very interesting. In the past, I have not noticed much similarity between transition tables for (most) BB champion machines (aside from the occational twin machines).

As to your prediction, I think it is an absolute certainty at this point that BBB(5, 2) > 10^36,534! I would go so far as to bet that even SB(5, 2) > 10^36,534 and furthermore I think it's very possible that SB(5, 2) > 10^10^10 (but finding such a machine will require a bit more technology!)

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

[Shawn Ligocki]

As with my previous analysis, we can ask the question, how lucky was this TM? And again, it was pretty lucky (Having reached G(1, 12601) allowed it to iterate 8391 times in stage 1 before having to do another stage 2 check). However, some other small starting configurations lead to even more "luck". Ex:

1. G(2, 2) -(8)-> G(1, 141) -(89)-> G(1, 21299239307978054624049)
2. G(3, 1) -(5)-> G(1,  45) -(29)-> G(1, 55728984)

Simulating the first one until it does the stage 2 test again seems pretty unattainable, but iterating the second seems within reason (it will take ~37 million iterations). If we did and it avoided spinning out, it would then be in a configuration like G(1, ~10^9000000) !

We can implement both of these pretty simply by adding on two states at the beginning to setup the tape we want. Specifically:

1. 1LB ---  1LD ---  1RD 1LE  0LF 0LD  0RG 0LC  0LG 1LF  1RG 1RC
   
2. 1RB ---  1LD ---  1RD 1LE  0LF 0LD  0RG 0LC  0LG 1LF  1RG 1RC
   

So, again we see two TMs which "probviously" spin out eventually, but we have no idea when. I will say that the first one iterates >10^22 times before getting its first chance to spin out, so even if it spun out the first time it reached stage 2, it would be in a config like G(>10^10^21, 0) and so the TM would have run for >10^(10^21) steps. And each time it resets at stage 2, we can roughly add one 10 to that tower of 10s.

[Shawn Ligocki]

Nick: Heh, I feel a bit like you are personally calling me out as a conspiracy theorist in this blog post :P

I suppose it is a bit odd to say that I believe something when all available evidence points against it, but consider a hypothetical Collatz Beaver Conjecture: That all Busy Beavers simulate Collatz-like functions. So far, the overwhelming majority of champions we've found can be analyzed as Collatz-like, but I don't think that's evidence that all Busy Beavers will be. Collatz-like functions appear to be an especially expressive and simple technology which have allowed explosive growth even for tiny TMs. But my intuition (or my humility) suggests to me that this is not the apex: as TM sizes grow, more powerful technologies will begin to take over.

That said, I really could believe either direction on the SCC. My intuition still falls on the side of Spaghetti code, but perhaps TMs which take more rigid/structured control of their simulation have an advantage by taking advantage of unique Mathematical facts. That said, with complicated enough Collatz-like behavior, I'm not entirely convinced that it is fair to call it structured (just because we can specify it Mathematically). As Pascal has mentioned, Collatz-like functions are Turing Complete when given enough rules.

But perhaps this is getting too philosophical again. We have a rigorous working definition of structured code, so maybe I need to spend a little bit of time investigating that.

In your simulations did you only run for Structured TMs (totally reducible)? Did that reduce your search space notably?

On Wed, Mar 16, 2022 at 2:57 PM Nicholas Drozd <nichol...@gmail.com> wrote:

[nichol...@gmail.com]

> Heh, I feel a bit like you are personally calling me out as a conspiracy theorist in this blog post :P

Haha no, actually I had in mind some other people I've talked to who insisted that SCC must be true. I think it's probably false, and you seem to be in the middle.

Of course we should keep an open mind in both directions! But the reasons for keeping an open mind also apply to the Collatz conjecture, despite its "probviousness". (I don't think this is an argument for general skepticism about open problems, but just about those of a certain complexity. The Collatz Conjecture is logically more complicated than Goldbach's Conjecture, for instance.)

> In your simulations did you only run for Structured TMs (totally reducible)? Did that reduce your search space notably?

Yeah, I filtered out everything with any graph complexity. So the fact that this one is simple counts as very very very weak evidence against SCC. I don't know how many machines were filtered out this way because I didn't keep any stats.

I've attached the CFG. It's pretty basic -- from state A you will eventually, one way or another, make your way to state E, and if you don't spin out, you will get back to A, and that's it. There are no fancy control flow tricks.

Now, on to the details of your analysis. Here's a slightly simpler way of stating the function:

    G(4k+0, m+2) -> G(7k+ 5, m)

    G(4k+1, m+2) -> G(7k+ 8, m+1)
    G(4k+2, m+2) -> G(7k+ 6, m+1)
    G(4k+3, m+2) -> G(7k+14, m)

    G(n, 1) -> G(1, n+3)
    G(n, 0) -> Spin Out

The only difference is changing the 4k + 4 line to 4k + 0. I'm pretty sure that's equivalent, but please double-check.

If I'm reading this right, does it mean that the tape becomes blank at some point? But when the machine spins out there are a handful of marks on the tape. (I'm not sure exactly how to interpret your interpreter!)

Can you tell exactly when it spins out vs when it quasihalts? When is its last non-E state reached compared to spin-out?

One thing that strikes me about this machine is that it prints a 0 on half of its 5x2 = 10 instructions. That's something I wouldn't have expected. My thinking has been that since there are infinitely many blanks on the tape, it's usually a bad idea to print a blank, particularly over a mark. That just undoes previous work and returns a cell to its "feral" state.

It could be that this machine proves that reasoning to be wrong. Or it could be that the reasoning is correct and that therefore this cannot be the true champion. I'm leaning towards the latter.

[Shawn Ligocki]

Your simplification of the Collatz function is correct ... I had originally thought it did something slightly different with G(0, m) ... but I think I was mistaken.

Can you tell exactly when it spins out vs when it quasihalts? When is its last non-E state reached compared to spin-out?

 

You will have to read between the lines a bit (since this is using a Macro Machine). My best suggestion is to use the (-b / --no-backsymbol) flag. You can also set the block size explicitly and there are a handful of other flags I find helpful. Ex, I ran the simulator as:

$ Code/Quick_Sim.py <(echo "1RB 1LC  0LD 0LB  0RE 0LA  0LE 1LD  1RE 1RA") --limited-rules -bn2 --verbose-simulator --no-steps | less -S

...

155971  00^inf 01^1 11^(~10^2040.0) <B 00^inf
155972  00^inf 01^1 <B 00^inf
155973  00^inf <D 00^inf
155974  00^inf 11^1 E> 00^inf 

 

So we can see that it certainly hits a blank tape (in state D). But in fact it hits a blank tape 3 times in a row as we can see by analyzing by hand starting at line 155972:

• 1 <B
• <B 0   [blank tape in state B]
• <D 00  [blank tape in state D]
• <E 000 [blank tape in state E]
• Spin out (since E0 -> 1RE)

So I believe it spins out on the same step as it quasihalts and it blanks the tape 2 steps earlier. I am considering adding software detection of these alternative halt times to the code ... but it is not trivial (mostly because of macro machines).

You can do the same sort of (by hand) analysis based off of the simulation with back-symbol macro machine:

$ Code/Quick_Sim.py <(echo "1RB 1LC  0LD 0LB  0RE 0LA  0LE 1LD  1RE 1RA") --limited-rules -n2 --verbose-simulator --no-steps | less -S

...

137217  00^inf 01^1 <B (00) 00^inf
137218  00^inf <D (00) 00^inf
137219  00^inf 11^1 (11) E> 00^inf 

you just have to be aware of what the notation means:

• 00^inf 01^1 <B (00) 00^inf is equivalent to the tape configuration:
• 0^inf 01 <B 00 0^inf which is equivalent to
• 0^inf 1 <B 0^inf
  

The parentheses just represent that we are including those symbols as part of the "Macro State".

One thing that strikes me about this machine is that it prints a 0 on half of its 5x2 = 10 instructions. That's something I wouldn't have expected. My thinking has been that since there are infinitely many blanks on the tape, it's usually a bad idea to print a blank, particularly over a mark. That just undoes previous work and returns a cell to its "feral" state.

As far as writing 0s vs. 1s. That's interesting. If you only ever write 1s you cannot encode much on the tape (basically just a single number in unary), so I do expect complex machines to take advantage of writing 0s. Likewise, over all 5x2 TMs, the most common count of transitions writing 0 will be half. That said, I would have guessed, like you, that the most successful TMs would write slightly more 1s than 0s.

One thing to note is that this machine uses "Macro Symbol" behavior. I wrote up my analysis with a tidy G() config, but the most common config you'll see while the machine is simulating is:

• F(a, b, c) = <E 0^a 10^b 1^c

In effect, we can say that this TM has built a third symbol (10) so that it can do more complex things than if it only had two symbols to work with. In order to take advantage of Macro Symbols, you need to write a lot of 0s :)

--

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/8e486e66-7786-41c1-8e8b-2ec946278ba1n%40googlegroups.com.

[Nicholas Drozd]

> In effect, we can say that this TM has built a third symbol (10) so that it can do more complex things than if it only had two symbols to work with. In order to take advantage of Macro Symbols, you need to write a lot of 0s :)

That is an extremely compelling argument against the "print marks
whenever possible" approach.

Actually this 01 idea can be seen with the naked eye just from looking
at the CFG. A and C clearly form a subroutine that operates on blocks
of 1s: A leaves the 1 a 1 and moves left and passes to C, which flips
the 1 to a 0 and moves left and passes back to A.

Something else to note about this program is that it reaches its last
instruction (C0) after 57 steps, which is the longest of any I've
checked so far. I'll try to gather more data on that.

And one more thing, the first move is to the right and the spin-out is
also to the right.

[Nicholas Drozd]

I looked further into when the top programs reach their last
instructions. This one, which quasihalts after 10^83 steps, reaches
its last instruction (E0) after 310 steps:

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

That's quite a bit later than any of the others in the 5x2-Beep-Top
list. Does it do anything interesting?

[Nicholas Drozd]

This raises an interesting question about Brady's algorithm. How long
should it be run? That is, how long should one wait when trying to
reach a program's last undefined instruction? For an N-state K-color
program the last instruction will be reached after BB(N, K) - 1 steps.
That's fine for 4x2, but for 5x2 it's not great!

I've been running mine for just 500 steps and discarding anything that
still has undefined instructions at that point. How far out have you
been running them?

[Nicholas Drozd]

> In your simulations did you only run for Structured TMs (totally reducible)? Did that reduce your search space notably?

I went back and regenerated my program list, this time keeping the
complicated ones. Out of 627,638 total "programs of interest", 563,629
are graph-reducible and 64,009 are not. So conjecturing that the
champion will be structured reduces the search space by about 10% --
nice, but not a game-changer.

Keep in mind that this list is restricted to programs that pass the
backward reasoning spin-out test, and so they are all zero-reflexive.
This already introduces some guaranteed graph-reducibility, so these
figures don't have any bearing on 5x2 program space as a whole.

I figured I would check and see if there was anything good among the
complicated programs, and lo, there was:

--> 1RB 1LC 1RD 0RA 0LC 1LE 1LA 0RE 0LA 1RB

That one spins out after 10^1089 steps. That's less than the champion,
but it takes about 100,000 more simulator steps to run (232,005). This
is definitely due to its complexity. Its CFG has an irreducible 3-node
kernel (states A, B, and E).

It's hard to simulate complex programs! This discovery has given me a
slight nudge back towards being agnostic about the SCC.

[Shawn Ligocki]

How long do you run Brady's algorithm? You never stop :) At least that's our strategy. Any time we simulate a TM, if we ever reach an undefined transition, we go right back to Brady's alg. to generate some more TMs. In this sense, Brady's algorithm is not a stage in our process (done before simulation). Instead it is constantly being used throughout simulation. That said, for 5x2 at least we think we know where it ends (with the current champion!) so once we've run all machines out to 47M steps we have some confidence that we're done.

So I wouldn't recommend throwing away everything that doesn't reach all transitions by 500 steps, but that will probably catch *most* machines.

[Shawn Ligocki]

Another cool machine, Nick! Here's my analysis:

1RB 1LC  1RD 0RA  0LC 1LE  1LA 0RE  0LA 1RB

Let

• F(a, b, c) = 0^inf 110^a 1^b 1010^c A> 0^inf

then:

• F(a  , 5k+0, c) -> F(a  , 8k+4c+1, 1)
• F(a  , 5k+1, c) -> F(a  , 8k+4c-4, 3) *
• F(a+1, 5k+2, c) -> F(a  , 8k+4c+9, 1)
• F(a  , 5k+3, c) -> F(a+1, 8k+4c+4, 0)
• F(a  , 5k+4, c) -> F(a  , 8k+4c+8, 0)

and

• F(0, 5k+2, c) -> 0^inf <C 1010^(2k+c+1) 1 -> Spin Out

(Note: * only applies if 8k+4c-4 >= 0. I didn't check what the rule is in the other case, it never comes up in the simulation of this orbit).

So, it's basically iterating a basic Collatz-like function on b (and c). But every time it hits a remainder of 3, it increases a. And every time it hits a remainder of 2, it decreases a. If it decrements a below 0, then it spins out.

It starts at config F(0, 1, 1) at step 10 and the orbit is:

• F(0, 1, 1)
  
• F(0, 0, 3)
• F(0, 13, 1)
• F(1, 24, 0)
• F(1, 40, 0)
• F(1, 65, 1)
• F(1, 109, 1)
• F(1, 180, 0)
• F(1, 289, 1)
• F(1, 468, 0)
• F(2, 748, 0)
• F(3, 1196, 0)
• F(3, 1908, 3)
• F(4, 3064, 0)
• F(4, 4904, 0)
• F(4, 7848, 0)
• F(5, 12556, 0)
• F(5, 20084, 3)
• F(5, 32148, 0)
• F(6, 51436, 0)
• F(6, 82292, 3)
• F(5, 131685, 1)
• ...
• F(8, 68378354472, 0)
• F(0, 372287172936448133, 1)
• F(12, 24504009587966134846185806292, 3)
• F(0, 5256720865102748386235587636850719350585741410092573433, 1)
• F(23, 265...7, 1)
• F(4, 999...3, 1)
• F(33, 149...2, 3)
• F(0, 40613768646873907603950896583526722897144840296028761542264666370371421621201079949652500661364855719209555020333339465473101422448892978623515482140598564564312507338978424647151213673376362631291950587322707883959351154735378695243727770558483234523983224220436016962816036122313505946791968045762134444342565949130264287673201564642552885629165214996991766851840205224246782413154514893359663522532844124668204309816604518074839592593227055800785478906754671791158810945268845582803819547597211127986037093931241679266845673816289226031705157, 1)

It runs 2,664 iterations before spinning out, has a wild roller-coaster ride, hitting a=0 several times and then rocketting up to a=33 at max before descending and finally crashing.

--
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/CABAiW0rVoyRQ-a66wrk2hC7ufk1PsPvKsuDNt3ErEREJKc-Kdw%40mail.gmail.com.

[Shawn Ligocki]

How "lucky" was this machine? It seems sort of like it's performing a random walk (stepping right every time the remainder is 3 and left every time the remainder is 2). In the case of this orbit, it takes 529 steps right and 530 steps left before finally falling off the a=0 cliff. I ran 1 million random walks and 2.4% of them ran this long. So we could say it's about 1/40 lucky (only 1/40 TMs which simulated a Collatz-like function like this would iterate as long).