Hydra

Unsolved problem:

Does Hydra run forever?

1RB3RB---3LA1RA_2LA3RA4LB0LB0LA (bbch)

Hydra is a BB(2,5) Cryptid. Similarly to Antihydra, it simulates repeatedly applying the function $H(n)=\lfloor \frac{3}{2}n\rfloor$, but starting at $n=3$ and swapping the roles of the even and odd terms of this sequence. The obstacles to proving whether or not this Turing machine halts are equally as serious as that machine.

Description

The transition table of Hydra.

Hydra basically tracks the progress of the integer ordered pair $(x,y)$ starting at $(3,0)$, which is represented on the tape as $x$ consecutive $0$s and to the right, $y$ consecutive $3$s. As time passes, the head moves back and forth, replacing those $0$s with $3$s, two at a time. Because the head visits a new cell on the left every time this happens, the number of $3$s on the tape is approximately $\frac{3}{2}x$ when this process finishes. From here, most of those $3$s are swiftly turned back into $0$s, generating a new ordered pair. However, there are two ways this could happen. If $x$ was even, then $y$ will decrease by one or halt Hydra if it drops below 0. Otherwise, $y$ will increase by 2. The problem of whether or not Hydra halts is unsolved, and can be restated like so:

If the quantities of even and odd numbers found are counted as the function $$\begin{array}{lll}h(2n)& =& 3n\\ h(2n+1)& =& 3n+1\end{array}$$ is applied continually, starting at 3, then does the count of even numbers ever exceed twice the count of odd numbers?

Attributions

Hydra and its high-level rules were first reported on Discord by Daniel Yuan on 20 April 2024.

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}$$ By scaling and translating these rules we acquire the Hydra function that relates it to Antihydra.

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.

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

To view an animation of the blank tape becoming $C(21,0)$ in 572 steps, click here.