Antihydra

Unsolved problem:

Does Antihydra run forever?

1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA (bbch)

Antihydra is a BB(6) Cryptid. Its pseudo-random behaviour was first reported on Discord by mxdys on 28 June 2024, and Racheline discovered the high-level rules soon after. It was named after the 2-state, 5-symbol Turing machine called Hydra for sharing many similarities to it.

Antihydra is known to not generate Sturmian words (Corollary 4).

Artistic depiction of Antihydra by Jadeix

0 1 A 1RB 1RA B 0LC 1LE C 1LD 1LC D 1LA 0LB E 1LF 1RE F --- 0RA The transition table of Antihydra.

A community trophy - to be awarded to the first person or group who solves the Antihydra problem

Analysis

Let $A(a,b):=0^{\mathrm{\infty }}{1}^{a}01^b\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$. Then, $$\begin{array}{lll}A(a,2b)& \stackrel{2a+3b^2+12b+11}{\to }& A(a+2,3b+2),\\ A(0,2b+1)& \stackrel{3b^2+9b-1}{\to }& 0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>F</mrow>}1101^{3b}{0}^{\mathrm{\infty }},\\ A(a+1,2b+1)& \stackrel{3b^2+12b+5}{\to }& A(a,3b+3).\end{array}$$

Proof

Consider the partial configuration $P(m,n):=01^m\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}01^n{0}^{\mathrm{\infty }}$. The configuration after two steps is $01^{m-1}0\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{1}^{n+1}{0}^{\mathrm{\infty }}$. We note the following shift rule: $$\begin{array}{c}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{1}^s\stackrel{s}{\to }{1}^s\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}\end{array}$$ As a result, we get $01^{m-1}01^{n+1}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$ after $n+1$ steps. Advancing two steps produces $01^{m-1}01^{n+2}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{0}^{\mathrm{\infty }}$. A second shift rule is useful here: $$\begin{array}{c}{1}^s\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}\stackrel{s}{\to }\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^s\end{array}$$ This allows us to reach $01^{m-1}0\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{n+2}{0}^{\mathrm{\infty }}$ in $n+2$ steps. Moving five more steps gets us to $01^{m-2}\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}01^{n+3}{0}^{\mathrm{\infty }}$, which is the same configuration as $P(m-2,n+3)$. Accounting for the head movement creates the condition that $m\ge 4$. In summary: $$\begin{array}{c}P(m,n)\stackrel{2n+12}{\to }P(m-2,n+3)\text{ if }m\ge 4.\end{array}$$ With $A(a,b)$ we have $P(b,0)$. As a result, we can apply this rule $\lfloor \frac{1}{2}b\rfloor -1$ times (assuming $b\ge 4$), which creates two possible scenarios:

1. If $b\equiv 0(\mathrm{mod}2)$, then in $\sum _{i=0}^{(b/2)-2}(2\times 3i+12)=\frac{3}{4}{b}^2+\frac{3}{2}b-6$ steps we arrive at $P(2,\frac{3}{2}b-3)$. The matching complete configuration is $0^{\mathrm{\infty }}{1}^{a}011\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}01^{(3b)/2-3}{0}^{\mathrm{\infty }}$. After $3b+4$ steps this is $0^{\mathrm{\infty }}{1}^a\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}001^{(3b)/2}{0}^{\mathrm{\infty }}$, which then leads to $0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{a}001^{(3b)/2}{0}^{\mathrm{\infty }}$ in $a$ steps. After five more steps, we reach $0^{\mathrm{\infty }}1\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{1}^{a+2}001^{(3b)/2}{0}^{\mathrm{\infty }}$, from which another shift rule must be applied:$$\begin{array}{c}\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{1}^s\stackrel{s}{\to }{1}^s\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}\end{array}$$Doing so allows us to get the configuration $0^{\mathrm{\infty }}{1}^{a+3}\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}001^{(3b)/2}{0}^{\mathrm{\infty }}$ in $a+2$ steps. In six steps we have $0^{\mathrm{\infty }}{1}^{a+2}011\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{1}^{(3b)/2}{0}^{\mathrm{\infty }}$, so we use the shift rule again, ending at $0^{\mathrm{\infty }}{1}^{a+2}01^{(3b)/2+2}\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, equal to $A(a+2,\frac{3}{2}b+2)$, $\frac{3}{2}b$ steps later. This gives a total of $2a+\frac{3}{4}{b}^2+6b+11$ steps.
2. If $b\equiv 1(\mathrm{mod}2)$, then in $\frac{3}{4}{b}^2-\frac{27}{4}$ steps we arrive at $P(3,\frac{3b-9}{2})$. The matching complete configuration is $0^{\mathrm{\infty }}{1}^{a}0111\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}01^{(3b-9)/2}{0}^{\mathrm{\infty }}$. After $3b+2$ steps this becomes $0^{\mathrm{\infty }}{1}^a\text{<mrow data-mjx-texclass="ORD"><mo><</mo>F</mrow>}1101^{(3b-3)/2}{0}^{\mathrm{\infty }}$. If $a=0$ then we have reached the undefined F0 transition with a total of $\frac{3}{4}{b}^2+3b-\frac{19}{4}$ steps. Otherwise, continuing for six steps gives us $0^{\mathrm{\infty }}{1}^{a-1}0111\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{1}^{(3b-3)/2}{0}^{\mathrm{\infty }}$. We conclude with the configuration $0^{\mathrm{\infty }}{1}^{a-1}01^{(3b+3)/2}\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, equal to $A(a-1,\frac{3b+3}{2})$, in $\frac{3b-3}{2}$ steps. This gives a total of $\frac{3}{4}{b}^2+\frac{9}{2}b-\frac{1}{4}$ steps.

The information above can be summarized as $$A(a,b)\to \{\begin{array}{ll}A(a+2,\frac{3}{2}b+2)& \text{if }b\ge 2,b\equiv 0(\mathrm{mod}2);\\ 0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>F</mrow>}1101^{(3b-3)/2}{0}^{\mathrm{\infty }}& \text{if }b\ge 3,b\equiv 1(\mathrm{mod}2),\text{ and }a=0;\\ A(a-1,\frac{3b+3}{2})& \text{if }b\ge 3,b\equiv 1(\mathrm{mod}2),\text{ and }a>0.\end{array}$$ Substituting $b\leftarrow 2b$ for the first case and $b\leftarrow 2b+1$ for the other two yields the final result.

In effect, the halting problem for Antihydra is about whether repeatedly applying the function $f(n)=\lfloor \frac{3n}{2}\rfloor +2$ will at some point produce more odd values of $n$ than twice the number of even values.

These rules can be modified to use the function $H(n)=\lfloor \frac{3n}{2}\rfloor$, or the Hydra function, which strengthens Antihydra's similarities to Hydra.

Trajectory

11 steps are required to enter the configuration $A(0,4)$ before the rules are repeatedly applied. So far, Antihydra has been simulated to $2^{31}$ rule steps, at which point $b=1073720884$. Here are the first few: $$\begin{array}{c}A(0,4)\stackrel{47}{\to }A(2,8)\stackrel{111}{\to }A(4,14)\stackrel{250}{\to }A(6,23)\stackrel{500}{\to }A(5,36)\stackrel{1209}{\to }A(7,56)\stackrel{2713}{\to }A(9,86)\to \cdots \end{array}$$ The trajectory of $b$ values resembles a random walk in which the walker can only move in step sizes +2 or -1 with equal probability, starting at position 0. If $P(n)$ is the probability that the walker will reach position -1 from position $n$, then it can be seen that $P(n)=\frac{1}{2}P(n-1)+\frac{1}{2}P(n+2)$. Solutions to this recurrence relation come in the form $P(n)=c_0{\left(\frac{\sqrt{5}-1}{2}\right)}^n+c_1+c_2{(-\frac{1+\sqrt{5}}{2})}^n$, which after applying the appropriate boundary conditions reduces to $P(n)={\left(\frac{\sqrt{5}-1}{2}\right)}^{n+1}$. This means that if the walker were to get to position 1073720884 then the probability of it ever reaching position -1 is ${\left(\frac{\sqrt{5}-1}{2}\right)}^{1073720885}\approx 4.841\times 10^{-224394395}$. This combined with the fact that the expected position of the walker after $k$ steps is $\frac{1}{2}k$ strongly suggests Antihydra probviously runs indefinitely.

Code

The following Python program implements the abstracted behavior of the Antihydra. Proving whether it halts or not would also solve the Antihydra problem:

# Current value of the iterated Hydra function starting with initial value 8
h = 8
# (Collatz-like) condition counter that keeps track of how many odd and even numbers have been encountered
c = 0
# If c equals -1 there have been (strictly) more than twice as many odd as even numbers and the program halts
while c != -1:
    # If h is even, add 2 to c so even numbers count twice
    if h % 2 == 0:
        c += 2
    else:
        c -= 1
    # Add the current hydra value divided by two (integer division, rounding down) to itself (Hydra function)
    # Note that integer division by 2 is equivalent to one bit shift to the right (h >> 1)
    h += h//2