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.