Consider the Collatz-like function:

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

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

\[3 \xrightarrow{O} 4 \xrightarrow{E} 6\xrightarrow{E} 9 \xrightarrow{O} 13 \xrightarrow{O} 19 \xrightarrow{O} 28 \xrightarrow{E} 42 \xrightarrow{E} 63 \cdots\]

where the Os and Es above each arrow represent whether we chose the Odd or Even rule to apply.

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

Solving the 2 state, 5 symbol Busy Beaver problem requires solving this Collatz-like problem! Specifically, we have a new Cryptid, the “Hydra”.

Hydra

Daniel Yuan (@dyuan01) first reported this TM on Discord on 20 Apr 2024. He named it “Hydra” after the famous Greek mythological beast. The machine definition is:

1RB3RB---3LA1RA_2LA3RA4LB0LB0LA (on bbchallenge)

  0 1 2 3 4
A 1RB 3RB — 3LA 1RA
B 2LA 3RA 4LB 0LB 0LA

It is one of the remaining 902 informal \(BB(2, 5)\) holdouts that Justin Blanchard recently shared on Discord which in turn was filtered down from my list of 23k holdouts.

Analysis

Let

\[A(a, b) = 0^\infty \; \text{ <B } \; 0^a \; 3^b \; 2 \; 0^\infty\]

Then the following rules apply:

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

Where these rules apply for any values \(n, b \ge 0\), “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 maps

One detail that jumps out to me about the Collatz-like behavior above, specifically that \(a\) is always divisible by 3. So we can rewrite this relation a bit:

Let

\[B(a, b) = A(3a, b) = 0^\infty \; \text{ <B } \; 0^{3a} \; 3^b \; 2 \; 0^\infty\]

Then:

\[\begin{array}{l} \text{Start} & & \xrightarrow{19} & B(1, 0) \\ B(2n, & 0) & \to & \text{Halt}(9n+3) \\ B(2n, & b+1) & \to & B(3n+1, b) \\ B(2n+1, & b) & \to & B(3n+2, b+2) \\ \end{array}\]

Furthermore, if you let

\[C(a, b) = B(a-2, b) = 0^\infty \; \text{ <B } \; 0^{3(a - 2)} \; 3^b \; 2 \; 0^\infty\]

then:

\[\begin{array}{l} \text{Start} & & \xrightarrow{19} & C(3, 0) \\ C(2n, & 0) & \to & \text{Halt}(9n-6) \\ C(2n, & b+1) & \to & C(3n, & b) \\ C(2n+1, & b) & \to & C(3n+1, & b+2) \\ \end{array}\]

For all \(n \ge 1\).

This recurrence has the elegant properties that

\[C(n, b) \to C(n + \left\lfloor \frac{n}{2} \right\rfloor, b^\prime)\]

and

\[\begin{array}{l} C(2^k, & b+k) & \to & C(3^k, & b) \\ C(2^k + 1, & b) & \to & C(3^k + 1, & b+2k) \\ \end{array}\]

Pseudo-random Walk

Much like Bigfoot, Hydra performs a pseudo-random walk using the parity from a Collatz-like function to determine which direction to walk. And like Bigfoot, that walk is biased so that after simulating for a while the apparent “probability” of halting is vanishingly small.

Specifically, we can see that the C rules above are simulating the Collatz-like function I described in the intro:

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

on it’s a parameter while keeping a sort of counter in the b parameter. Every time you apply an Odd rule, \(b \to b+2\). Every time you apply an Even rule, \(b \to b-1\). Hydra only halts if you ever end up with \(b < 0\).

If you simulate this recurrence for 4 million steps you get a value:

\[C(> 10^{704\,365}, 2\,005\,373)\]

Probviously Not Halting

Just like with Bigfoot, if we consider this to be a truly random walk where half the time it walks one step left and half the time 2 steps right, then the chance of ever reaching \(b < 0\) when starting from \(b = n\) is \((\frac{1}{2})^{n+1}\). So, the chance of coming back from \(b = 2\,005\,373\) would be the minute fraction \((\frac{1}{2})^{2\,005\,374}\).

Thus Hydra “probviously” never halts. But to prove it you would have to prove a Collatz-like problem.

Comparison to Bigfoot

Hydra’s behavior is quite similar to Bigfoot’s as described already in this article. The main difference is that Hydra computes a much simpler (and I would say more elegant) Collatz-like function. In fact it is almost the simplest possible Collatz-like function!

My article about Bigfoot actually got quite a bit of attention being posted to Hacker News and Reddit r/math where it got over 100 comments! Among these there was a reasonably common theme summed up well by this comment:

nneonneo: Probably more accurate to say that BB(3, 3) looks hard; that is, it encodes a Collatz-type problem, and many Collatz-type problems are very hard to solve (including, of course, the classic Collatz conjecture). However, this instance might not necessarily be hard. For one, the behaviour seems to be heavily biased; for another, we only have to consider a single trajectory instead of the trajectories for all integers (as with the classic Collatz problem).

Which is totally true! These Cryptids simulate problems that appear (subjectively) to be hard. But maybe they are not. Perhaps these specific Collatz-like questions have a clever solution. Hydra helps to remove at least one of nneonneo’s caveats: Hydra’s Collatz-like function is extremely simple and does not follow any specific pattern (like the odd, odd, even, even pattern that Bigfoot followed).

A Bonus Cryptid

A few days after discovering Hydra, Daniel found another BB(2, 5) Cryptid:

1RB3RB---3LA1RA_2LA3RA4LB0LB1LB

Define
A(a, b) = 0^inf <B 0^a 3^b 2 0^inf

The rules are
A(3n, 0) -> Halt
A(3n, b+1) -> A(4n+3, b)
A(3n+1, b) -> A(4n+3, b+3)
A(3n+2, 0) -> ?
A(3n+2, b+1) -> A(4n+5, b)

Starts: A(3, 1)

I have not looked into analyzing this one yet, but wanted to share it since AFAIK it is only the 3rd Cryptid discovered (after Bigfoot and Hydra).