Hydra

Unsolved problem:

Does Hydra run forever?

1RB3RB---3LA1RA_2LA3RA4LB0LB0LA (bbch)

Hydra is a BB(2,5) Cryptid. Its high-level rules were first reported on Discord by Daniel Yuan on 20 April 2024, who also gave Hydra said name. Later on, a 6-state, 2-symbol Turing machine was discovered and named Antihydra for having similar behaviour to Hydra, making the study of this machine important to the study of that one.

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

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

The transition table of Hydra.

Analysis

Let $C(a,b):=0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}20^a{3}^{b}20^{\mathrm{\infty }}$. Then, $$\begin{array}{lll}C(2a,0)& \stackrel{6a^2+20a+4}{\to }& 0^{\mathrm{\infty }}{3}^{3a+1}1\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}20^{\mathrm{\infty }},\\ C(2a,b+1)& \stackrel{6a^2+23a+10}{\to }& C(3a+3,b),\\ C(2a+1,b)& \stackrel{4b+6a^2+23a+26}{\to }& C(3a+3,b+2).\end{array}$$

Proof

Consider the partial configuration $P(m,n):=0^{\mathrm{\infty }}{3}^m\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}020^n$. After 14 steps this configuration becomes $0^{\mathrm{\infty }}{3}^{m+3}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}20^{n-2}$. We note the following shift rule: $$\begin{array}{c}{3}^s\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}\stackrel{s}{\to }\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{3}^s\end{array}$$ Using this shift rule, we get $0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{3}^{m+3}20^{n-2}$ in $m+3$ steps. From here, we can observe that $\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}03^s$ turns into $3\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}03^{s-1}$ in three steps if $s\ge 1$. By repeating this process, we acquire this transition rule: $$\begin{array}{c}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}03^s\stackrel{3s}{\to }{3}^s\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}0\end{array}$$ With this rule, it takes $3m+9$ steps to reach the configuration $0^{\mathrm{\infty }}{3}^{m+3}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}020^{n-2}$, which is the same configuration as $P(m+3,n-2)$. To summarize: $$\begin{array}{c}P(m,n)\stackrel{4m+26}{\to }P(m+3,n-2)\text{ if }n\ge 2.\end{array}$$ With $C(a,b)$ we have $P(0,a)$. As a result, we can apply this rule $\lfloor \frac{1}{2}a\rfloor$ times, which creates two possible scenarios:

1. If $a\equiv 0(\mathrm{mod}2)$, then in $\sum _{i=0}^{(a/2)-1}(4\times 3i+26)=\frac{3}{2}{a}^2+10a$ steps we arrive at $P(\frac{3}{2}a,0)$. The matching complete configuration is $0^{\mathrm{\infty }}{3}^{(3/2)a}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}023^{b}20^{\mathrm{\infty }}$, which in four steps becomes $0^{\mathrm{\infty }}{3}^{(3/2)a+1}1\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{3}^{b}20^{\mathrm{\infty }}.$ If $b=0$ then we have reached the undefined A2 transition in $\frac{3}{2}{a}^2+10a+4$ steps total. Otherwise, continuing for three steps gives us $0^{\mathrm{\infty }}{3}^{(3/2)+2}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>B</mrow>}03^{b-1}20^{\mathrm{\infty }}$. Another shift rule is required here:$$\begin{array}{c}{3}^s\text{<mrow data-mjx-texclass="ORD"><mo><</mo>B</mrow>}\stackrel{s}{\to }\text{<mrow data-mjx-texclass="ORD"><mo><</mo>B</mrow>}{0}^s\end{array}$$This means the configuration becomes $0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>B</mrow>}{0}^{(3/2)a+3}{3}^{b-1}20^{\mathrm{\infty }}$ in $\frac{3}{2}a+2$ steps, and $0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}20^{(3/2)a+3}{3}^{b-1}20^{\mathrm{\infty }}$, equal to $C(\frac{3}{2}a+3,b-1)$, one step later. This gives a total of $\frac{3}{2}{a}^2+\frac{23}{2}a+10$ steps.
2. If $a\equiv 1(\mathrm{mod}2)$, then in $\frac{3}{2}{a}^2+7a-\frac{17}{2}$ steps we arrive at $P(\frac{3a-3}{2},1)$. The matching complete configuration is $0^{\mathrm{\infty }}{3}^{(3a-3)/2}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}0203^{b}20^{\mathrm{\infty }}$, which in four steps becomes $0^{\mathrm{\infty }}{3}^{(3a-1)/2}1\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}03^{b}20^{\mathrm{\infty }}$, and then $0^{\mathrm{\infty }}{3}^{(3a-1)/2}13^b\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}020^{\mathrm{\infty }}$ in $3b$ steps. After 14 steps, we see the configuration $0^{\mathrm{\infty }}{3}^{(3a-1)/2}13^{b+3}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}20^{\mathrm{\infty }}$, which turns into $0^{\mathrm{\infty }}{3}^{(3a-1)/2}1\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{3}^{b+3}20^{\mathrm{\infty }}$ in $b+3$ steps. In two steps we get $0^{\mathrm{\infty }}{3}^{(3a+1)/2}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>B</mrow>}03^{b+2}20^{\mathrm{\infty }}$, followed by $0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>B</mrow>}{0}^{(3a+3)/2}{3}^{b+2}20^{\mathrm{\infty }}$ after $\frac{3a+1}{2}$ more steps. We conclude with $0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}20^{(3a+3)/2}{3}^{b+2}20^{\mathrm{\infty }}$, equal to $C(\frac{3a+3}{2},b+2)$, one step later. This gives a total of $4b+\frac{3}{2}{a}^2+\frac{17}{2}a+16$ steps.

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

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

An alternative version of these rules exists that makes the connection to Antihydra more apparent by using the function $H(n)=\lfloor \frac{3}{2}n\rfloor$, or the Hydra function.

Trajectory

It takes 20 steps to reach the configuration $C(3,0)$, and from there, the Collatz-like rules are repeatedly applied. Simulating Hydra has shown that after 4000000 rule steps, we have $b=2005373$. Here are the first few: $$\begin{array}{c}C(3,0)\stackrel{55}{\to }C(6,2)\stackrel{133}{\to }C(12,1)\stackrel{364}{\to }C(21,0)\stackrel{856}{\to }C(33,2)\stackrel{1938}{\to }C(51,4)\stackrel{4367}{\to }C(78,6)\to \cdots \end{array}$$ The heuristic argument that suggests Antihydra is a probviously non-halting machine can be applied here. This means that if $b$ is to be thought of as moving randomly, then the probability of Hydra halting is ${\left(\frac{\sqrt{5}-1}{2}\right)}^{2005374}\approx 4.168\times 10^{-419099}$.

Code

Fast Hydra/Antihydra simulation code by Greg Kuperberg (who said it could be made faster using FLINT):

# Python script to demonstrate almost linear time hydra simulation
# using fast multiplication. 
# by Greg Kuperberg

import time
from gmpy2 import mpz,bit_mask

# Straight computation of t steps of hydra
def simple(n,t):
    for s in range(t): n += n>>1
    return n

# Accelerated computation of 2**e steps of hydra
def hydra(n,e):
    if e < 9: return simple(n,1<<e)
    t = 1<<(e-1)
    (p3t,m) = (mpz(3)**t,bit_mask(t))
    n = p3t*(n>>t) + hydra(n&m,e-1)
    return p3t*(n>>t) + hydra(n&m,e-1)

def elapsed():
    (last,elapsed.mark) = (elapsed.mark,time.process_time())
    return elapsed.mark-last
elapsed.mark = 0

(n,e) = (mpz(3),25)

elapsed()
print('hydra:  steps=%d hash=%016x time=%.6fs'
    % (1<<e,hash(hydra(n,e)),elapsed()))

# Quadratic time algorithm for comparison
# print('simple: steps=%d hash=%016x time=%.6fs'
#     % (1<<e,hash(simple(n,1<<e)),elapsed()))