BB(6)

The 6-state, 2-symbol Busy Beaver problem BB(6) is unsolved. With the discovery of Antihydra in 2024, we now know that we must solve a Collatz-like problem in order to solve BB(6).

The current BB(6) champion 1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE (bbch) was discovered by Pavel Kropitz in 2022 proving the lower bound:

$$S(6)>\Sigma (6)>10\uparrow \uparrow 15$$

Techniques

In order to simulate the current BB(6) champion requires accelerated simulation that can handle Collatz Level 2 inductive rules. In other words, it requires a simulator that can prove the rules:

$${\begin{array}{l}C(4k)&\to &Halt({\frac {3^{k+3}-11}{2}})\\C(4k+1)&\to &C({\frac {3^{k+3}-11}{2}})\\C(4k+2)&\to &C({\frac {3^{k+3}-11}{2}})\\C(4k+3)&\to &C({\frac {3^{k+3}+1}{2}})\\\end{array}}$$

and also compute the remainder mod 3 of numbers produced by applying these rules 15 times (which requires some fancy math related to Euler's_totient_function).

Cryptids

There have been quite a few Cryptids found in the BB(6) search space. None of them are known definitively to halt or run forever. Proving whether or not they halt would require solving a Collatz-like problem in order to be tractable. However, using probabilistic assumptions they have been categorized into either probviously halting or probviously non-halting.

Probviously halting Collatz-like Cryptids:

• 1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC (bbch) (and 15 related TMs) a family of probviously halting cryptids

Probviously non-halting Collatz-like Cryptids:

• Antihydra
• 1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA (bbch) a variant of Hydra and Antihydra
• 1RB1LD_1RC1RE_0LA1LB_0LD1LC_1RF0RA_---0RC (bbch) similar to Antihydra
• 1RB0LD_1RC1RF_1LA0RA_0LA0LE_1LD1LA_0RB--- (bbch) similar to Antihydra
• 1RB0LB_1LC0RE_1LA1LD_0LC---_0RB0RF_1RE1RB (bbch) similar to Antihydra

There are also a number of machines which also appear to depend upon different (not Collatz-like) apparently chaotic behavior and so also appear to be Cryptids. However, nobody has yet proposed a clear analysis of how their behavior is connected to open mathematical problems (like Collatz-like problems).

Potential Cryptids:

• 1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE (bbch)
• 1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE (bbch)
• 1RB0RB_1LC1RE_1LF0LD_1RA1LD_1RC1RB_---1LC (bbch)
• 1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD (bbch)

Top Halters

The current top 10 BB(6) halters (known by Shawn Ligocki) are:

Top Known BB(6) Halters

TM	approximate sigma score
1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE (bbch)	~10↑↑15.60465
1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA (bbch)	~10↑↑7.23619
1RB0LA_1LC1LF_0LD0LC_0LE0LB_1RE0RA_1RZ1LD (bbch)	~10↑↑5.63534
1RB1RE_1LC1LF_1RD0LB_1LE0RC_1RA0LD_1RZ1LC (bbch)	~10↑↑5.56344
1RB0LE_0RC1RA_0LD1RF_1RE0RB_1LA0LC_0RD1RZ (bbch)	~10↑↑5.12468
1RB0RF_1LC1LB_0RE0LD_0LC0LB_0RA1RE_0RD1RZ (bbch)	~10↑↑5.03230
1RB1LA_1LC0RF_1LD1LC_1LE0RE_0RB0LC_1RZ1RA (bbch)	~10↑↑4.91072
1RB0LE_1LC1RA_1RE0LD_1LC1LF_1LA0RC_1RZ1LC (bbch)	~10↑↑3.33186
1RB1RF_1LC1RE_0LD1LB_1LA0RA_0RA0RB_1RZ0RD (bbch)	~10↑↑3.31128
1RB0LF_1LC0RA_1RD0LB_1LE1RC_1RZ1LA_1LA1LE (bbch)	~10↑↑3.18855

Runtimes are not available, but are presumed to be about $score^{2}$ which is roughly indistinguishable in tetration notation. Fractional tetration notation is described in "Extending Up-arrow Notation". For a longer list of halting TMs see https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/6x2.txt. For historical perspective see Pascal Michel's Historical survey of Busy Beavers.

Holdouts

@mxdys's informal holdouts list is down to 4408 TMs as of 8 Nov 2024.