Note: All Discord links are for the https://bbchallenge.org/ Discord server.

Consider the Collatz-like function:

\[\begin{array}{l} f(2n) & = & 3n \\ f(2n+1) & = & 3n+1 \\ \end{array}\]

or equivalently defined as

\[f(n) = n + \left\lfloor \frac{n}{2} \right\rfloor\]

Starting from 8 and repeatedly applying \(f\) we get the infinite sequence:

\[8 \xrightarrow{E} 12 \xrightarrow{E} 18 \xrightarrow{E} 27 \xrightarrow{O} 40 \xrightarrow{E} 60 \xrightarrow{E} 90 \xrightarrow{E} 135 \xrightarrow{O} 202 \cdots\]

where the Os and Es above each arrow represent whether we chose the Odd or Even rule to apply (i.e. whether or not the previous value was odd or even).

Starting from 8, will you ever reach a point where the cumulative number of Os applied is greater than twice the number of Es applied?

Solving the 6-state, 2-symbol Busy Beaver problem requires solving this Collatz-like problem! Yes, that’s right, we have our first BB(6) Cryptid, the “Antihydra”.

For returning visitors who may be feeling a sense of Deja-Vu: Yes, this is almost identical to the Hydra rules! In fact, the only difference is that Antihydra starts at 8 instead of 3 and that the halting condition is “reversed” (\(2O > E\) instead of \(2E > O\)).

Antihydra

1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA (on bbchallenge)

  0 1
A 1RB 1RA
B 0LC 1LE
C 1LD 1LC
D 1LA 0LB
E 1LF 1RE
F — 0RA

This TM was discovered and shared by @mxdys on 28 June 2024 on Discord with the message: “This TM looks like a random [walk] like hydra”. Shortly afterwards, Racheline (@rae) discovered and shared the precise rules described below.

Analysis

Let

\[E(a, b) = 0^\infty \; 1^b \; 0 \; 1^a \; \text{E>} \; 0^\infty\]

Then the following rules apply:

\[\begin{array}{l} \text{Start} & & \xrightarrow{11} & E(4, 0) \\ E(2n, & b) & \to & E(3n+2, b+2) & \text{ if } n \ge 1 \\ E(2n+1, & 0) & \to & \text{Halt}(3n+3) & \text{ if } n \ge 1 \\ E(2n+1, & b+1) & \to & E(3n+3, b) & \text{ if } n \ge 1 \\ \end{array}\]

Where “Start” is the TM in state A on a blank tape and “Halt(x)” means the TM halts with \(x\) non-zero symbols on the tape.

Alternative Collatz map

Like with Hydra, we can shift this map to produce a more familiar mapping.

Let

\[A(a, b) = E(a-4, b)\]

then for all \(n \ge 3\) and \(b \ge 0\) we have:

\[\begin{array}{l} \text{Start} & & \xrightarrow{11} & A(8, 0) \\ A(2n, & b) & \to & A(3n, b+2) \\ A(2n+1, & 0) & \to & \text{Halt}(3n-3) \\ A(2n+1, & b+1) & \to & A(3n+1, b) \\ \end{array}\]

which is (as previously stated) the same as the Hydra map, but starting from 8 and with the reverse halting condition.

Note that the \(n \ge 3\) conditions does not cause any trouble since this iteration starts at \(a = 8\) and \(a\) strictly increases after each iteration (for all \(a \ge 2\)).

Trajectory

@mxdys has simulated this iteration out to \(2^{31} = 2\,147\,483\,648\) steps at which point \(b = 1\,073\,720\,884\) (only 20940 below the expected value if this were a random walk) (Discord link). As with Hydra and Bigfoot, if we treat this iteration as a random walk, it has a miniscule chance of ever returning to \(b = 0\) and thus of ever halting.

The Future of Busy Beaver

On Tuesday, we at bbchallenge.org announced a Coq proof of the BB(5) problem (and Ben Brubaker at Quanta wrote a lovely article describing the 60 year journey!). And within a week before that, we have also found this first BB(6) Cryptid. This combination of events leaves me with some sadness alongside my joy. One of the things I’ve long talked about loving when it comes to the Busy Beaver problem, is the idea that we will never be done with it. Nobody can ever find all Busy Beaver values, so there will always be one more puzzle to solve, one more mystery to explore.

But with this discovery of Cryptids in BB(6), we now know (in an especially concrete way) how the next puzzle will be quite hard. Scott Aaronson is quoted in Ben’s article saying “It’s conceivable that this is the last busy beaver number that we will ever know.” Is this the end of the Busy Beaver problem? Instead of an end I think it is a sharp turn on the racecourse. Up until now, our goal has been to find new Busy Beaver champions and prove that all other TMs run forever. Now, it feels, that our goal has changed slightly: in addition to finding new champions, we are also looking for new Cryptids and trying to explain them in as simple a way as possible.

Solving BB(6) feels out of reach in my lifetime, but solving BB(6) modulo a handful of Cryptids feels possible. As Busy Beaver hunters in a changing world, we must adapt to the new conditions and consider new prey. Let us also hunt Cryptids!