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.

	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 nonhalting 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}$.