Antihydra

Unsolved problem:

Does Antihydra run forever?

Artistic depiction of Antihydra by Jadeix

Antihydra (1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA (bbch)) is a probviously nonhalting BB(6) Collatz-like Cryptid. In fact, it was the first identified BB(6) Cryptid. It is closely related to Hydra.

It simulates iterations of the Collatz-like Hydra function:

$$H(n)=\left\lfloor {\frac {3n}{2}}\right\rfloor ={\begin{cases}{\frac {3n}{2}}&{\text{if }}n{\text{ even}}\\{\frac {3n-1}{2}}&{\text{if }}n{\text{ odd}}\\\end{cases}}$$

starting from 8:

$$8\to 12\to 18\to 27\to 40\to 60\to 90\to 135\to 202\cdots$$

Antihydra halts if and only if the cumulative number of odd values in this sequence is ever more than twice the cumulative number of even values.

If we treat the parity of successive values in this sequence as independent random coin flips, then this is a biased random walk and has a miniscule chance of ever halting, thus we say that this TM "probviously" does not halt. But proving this would require solving a Collatz-like problem.

Turing Machine

Antihydra is the TM 1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA (bbch)

Antihydra

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

It was discovered by @mxdys on 28 Jun 2024 and shared on Discord and Racheline discovered that it iterates the Hydra function.

Analysis

Binary representation of the first 1000 steps of the evolution of the exponentially increasing variable of the Antihydra iteration (a = a + a//2), the colored background indicating whether the value is even (blue) or odd (red)

Let $A(a+4,b)=0^{\infty }\;1^{b}\;0\;1^{a}\;E>\;0^{\infty }$, then

$${\begin{array}{l}{\text{Start}}&&\to &A(8,&0)\\A(2a,&b)&\to &A(3a,&b+2)\\A(2a+1,&b)&\to &A(3a+1,&b-1)&{\text{if}}&b>0\\A(2a+1,&0)&\to &{\text{HALT}}\end{array}}$$

At each iteration, $a\mapsto H(a)$ and

$$b\mapsto {\begin{cases}b+2&{\text{if }}a{\text{ is even}}\\b-1&{\text{if }}a{\text{ is odd}}\\\end{cases}}$$

halting iff b ever reaches -1.

Biased Random Walk

If we consider the sequence of parities of $a$ to be independent random coin flips, then the movement of $b$ is a biased random walk (50% chance of +2, 50% of -1). Starting from $b=n$, the chance of such a random walk ever reaching $b=-1$ is $\left({\frac {1}{\phi }}\right)^{n+1}$ and the expected value of b after k steps is ${\frac {k}{2}}$.

Simulation

@mxdys has simulated this iteration out to $2^{31}=2\,147\,483\,648$ steps at which point $b=1\,073\,720\,884$ (Discord link), this is 20940 (0.002%) below the expected value if this were a random walk. If this was a random walk, the chance of ever halting from this point is

$$\left({\frac {1}{\phi }}\right)^{1\,073\,720\,885}<\left({\frac {1}{2}}\right)^{500\,000\,000}$$

an extremely miniscule chance.