Hydra

Unsolved problem:

Does Hydra run forever?

1RB3RB---3LA1RA_2LA3RA4LB0LB0LA (bbch)

Hydra is a BB(2,5) Cryptid. It simulates computing the terms of the sequence

$$H_{n+1}={\bigg \lfloor }{\frac {3}{2}}H_{n}{\bigg \rfloor },H_{0}=3,$$

halting if and only if there exists a point in the sequence where the number of even terms up to that point exceeds twice the number of odd terms.

Analysis

Rules

Let $C(a,b):=0^{\infty }\;{\textrm {<A}}\;2\;0^{a}\;3^{b}\;2\;0^{\infty }$. Then,

$${\begin{array}{|lll|}\hline C(2a,0)&\xrightarrow {6a^{2}+20a+4} &0^{\infty }\;3^{3a+1}\;1\;{\textrm {A>}}\;2\;0^{\infty },\\C(2a,b+1)&\xrightarrow {6a^{2}+23a+10} &C(3a+3,b),\\C(2a+1,b)&\xrightarrow {4b+6a^{2}+23a+26} &C(3a+3,b+2).\\\hline \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^{\infty }\;3^{m}\;{\textrm {A>}}\;02\;0^{n}$. After 14 steps this configuration becomes $0^{\infty }\;3^{m+3}\;{\textrm {<A}}\;2\;0^{n-2}$. We note the following shift rule:

$${\begin{array}{|c|}\hline 3^{s}\;{\textrm {<A}}\xrightarrow {s} {\textrm {<A}}\;3^{s}\\\hline \end{array}}$$

Using this shift rule, we get $0^{\infty }\;{\textrm {<A}}\;3^{m+3}\;2\;0^{n-2}$ in $m+3$ steps. From here, we can observe that ${\textrm {A>}}\;0\;3^{s}$ turns into $3\;{\textrm {A>}}\;0\;3^{s-1}$ in three steps if $s\geq 1$. By repeating this process, we acquire this transition rule:

$${\begin{array}{|c|}\hline {\textrm {A>}}\;0\;3^{s}\xrightarrow {3s} 3^{s}\;{\textrm {A>}}\;0\\\hline \end{array}}$$

With this rule, it takes $3m+9$ steps to reach the configuration $0^{\infty }\;3^{m+3}\;{\textrm {A>}}\;02\;0^{n-2}$, which is the same configuration as $P(m+3,n-2)$. To summarize:

$${\begin{array}{|c|}\hline P(m,n)\xrightarrow {4m+26} P(m+3,n-2){\text{ if }}n\geq 2.\\\hline \end{array}}$$

With $C(a,b)$ we have $P(0,a)$. As a result, we can apply this rule ${\textstyle {\big \lfloor }{\frac {1}{2}}a{\big \rfloor }}$ times, which creates two possible scenarios:

1. If $a\equiv 0\ (\operatorname {mod} 2)$, then in $\sum _{i=0}^{(a/2)-1}(4\times 3i+26)=\textstyle {\frac {3}{2}}a^{2}+10a$ steps we arrive at ${\textstyle P{\Big (}{\frac {3}{2}}a,0{\Big )}}$. The matching complete configuration is $0^{\infty }\;3^{(3/2)a}\;{\textrm {A>}}\;02\;3^{b}\;2\;0^{\infty }$, which in four steps becomes $0^{\infty }\;3^{(3/2)a+1}\;1\;{\textrm {A>}}\;3^{b}\;2\;0^{\infty }.$ If $b=0$ then we have reached the undefined A2 transition in ${\textstyle {\frac {3}{2}}a^{2}+10a+4}$ steps total. Otherwise, continuing for three steps gives us $0^{\infty }\;3^{(3/2)+2}\;{\textrm {<B}}\;0\;3^{b-1}\;2\;0^{\infty }$. Another shift rule is required here:
   $${\begin{array}{|c|}\hline 3^{s}\;{\textrm {<B}}\xrightarrow {s} {\textrm {<B}}\;0^{s}\\\hline \end{array}}$$
   This means the configuration becomes $0^{\infty }\;{\textrm {<B}}\;0^{(3/2)a+3}\;3^{b-1}\;2\;0^{\infty }$ in ${\textstyle {\frac {3}{2}}a+2}$ steps, and $0^{\infty }\;{\textrm {<A}}\;2\;0^{(3/2)a+3}\;3^{b-1}\;2\;0^{\infty }$, equal to ${\textstyle C{\Big (}{\frac {3}{2}}a+3,b-1{\Big )}}$, one step later. This gives a total of ${\textstyle {\frac {3}{2}}a^{2}+{\frac {23}{2}}a+10}$ steps.
2. If $a\equiv 1\ (\operatorname {mod} 2)$, then in ${\textstyle {\frac {3}{2}}a^{2}+7a-{\frac {17}{2}}}$ steps we arrive at ${\textstyle P{\Big (}{\frac {3a-3}{2}},1{\Big )}}$. The matching complete configuration is $0^{\infty }\;3^{(3a-3)/2}\;{\textrm {A>}}\;020\;3^{b}\;2\;0^{\infty }$, which in four steps becomes $0^{\infty }\;3^{(3a-1)/2}\;1\;{\textrm {A>}}\;0\;3^{b}\;2\;0^{\infty }$, and then $0^{\infty }\;3^{(3a-1)/2}\;1\;3^{b}\;{\textrm {A>}}\;02\;0^{\infty }$ in $3b$ steps. After 14 steps, we see the configuration $0^{\infty }\;3^{(3a-1)/2}\;1\;3^{b+3}\;{\textrm {<A}}\;2\;0^{\infty }$, which turns into $0^{\infty }\;3^{(3a-1)/2}\;1\;{\textrm {<A}}\;3^{b+3}\;2\;0^{\infty }$ in $b+3$ steps. In two steps we get $0^{\infty }\;3^{(3a+1)/2}\;{\textrm {<B}}\;0\;3^{b+2}\;2\;0^{\infty }$, followed by $0^{\infty }\;{\textrm {<B}}\;0^{(3a+3)/2}\;3^{b+2}\;2\;0^{\infty }$ after another ${\textstyle {\frac {3a+1}{2}}}$ steps. We conclude with $0^{\infty }\;{\textrm {<A}}\;2\;0^{(3a+3)/2}\;3^{b+2}\;2\;0^{\infty }$, equal to ${\textstyle C{\Big (}{\frac {3a+3}{2}},b+2{\Big )}}$, one step later. This gives a total of ${\textstyle 4b+{\frac {3}{2}}a^{2}+{\frac {17}{2}}a+16}$ steps.

The information above can be summarized as

$$C(a,b)\rightarrow {\begin{cases}0^{\infty }\;3^{(3/2)a+1}\;1\;{\textrm {A>}}\;2\;0^{\infty }&{\text{if }}a\equiv 0{\pmod {2}}{\text{ and }}b=0,\\C{\Big (}{\frac {3}{2}}a+3,b-1{\Big )}&{\text{if }}a\equiv 0{\pmod {2}}{\text{ and }}b>0,\\C{\Big (}{\frac {3a+3}{2}},b+2{\Big )}&{\text{if }}a\equiv 1{\pmod {2}}.\end{cases}}$$

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. Here are the first few iterations:

Animation of the blank tape becoming $C(21,0)$ in 572 steps (click to view).

$${\begin{array}{|c|}\hline C(3,0)\xrightarrow {55} C(6,2)\xrightarrow {133} C(12,1)\xrightarrow {364} C(21,0)\xrightarrow {856} C(33,2)\xrightarrow {1938} C(51,4)\rightarrow \cdots \\\hline \end{array}}$$

After 60 million rule steps, there are 29995836 even values of $a$ and 30004165 odd values, giving a very high $b$ value. However, this does not sufficiently prove that Hydra does not halt.

A heuristic nonhalting argument

The trajectory of $b$ values can be approximated by a random walk, where the walker can only move in step sizes +2 or -1 with equal probability, starting at position 0. The expected position of the walker after $k$ steps is ${\textstyle {\frac {1}{2}}k}$, and it can be shown that the probability of the walker reaching position -1 from position $n$ is ${\textstyle {{\Big (}{\frac {{\sqrt {5}}-1}{2}}{\Big )}}^{n+1}}$.

Proof

Let $P(n)$ denote the probability of the random walker reaching position 0 from position $n$. If the walker reaches position 0, it will do so either by first moving +2 with probability ${\textstyle {\frac {1}{2}}}$ or first moving -1 with probability ${\textstyle {\frac {1}{2}}}$. Therefore, the recurrence relation is

$$\textstyle P(n)={\frac {1}{2}}P(n+2)+{\frac {1}{2}}P(n-1){\text{ for }}n\geq 1.$$

Bringing all terms with $P$ to the left side of the equation and then substituting $n\leftarrow n+1$ gives

$$\textstyle P(n+1)-{\frac {1}{2}}P(n+3)-{\frac {1}{2}}P(n)=0.$$

This equation has the form $\sum _{i=0}^{k}a_{i}P(n+i)=0$, which can be solved using the zeroes of the characteristic polynomial $f(z)=\sum _{i=0}^{k}a_{i}z^{i}$. In this instance we get ${\textstyle f(z)=-{\frac {1}{2}}+z-{\frac {1}{2}}z^{3}}$, whose zeroes are given by

$$\textstyle z_{0}={\frac {{\sqrt {5}}-1}{2}},\qquad \qquad z_{1}=1,\qquad \qquad z_{2}=-{\frac {1+{\sqrt {5}}}{2}}.$$

For each real root $z_{i}$ with multiplicity 1, its fundamental solution is $c_{i}{\left(z_{i}\right)}^{n}$, and combining these fundamental solutions produces the general solution. Therefore,

$$\textstyle P(n)=c_{0}{\left({\frac {{\sqrt {5}}-1}{2}}\right)}^{n}+c_{1}+c_{2}{\left(-{\frac {1+{\sqrt {5}}}{2}}\right)}^{n}$$

The boundary condition $\lim _{n\to \infty }P(n)=0$ means $c_{2}=0$ (since ${\textstyle \left\vert -{\frac {1+{\sqrt {5}}}{2}}\right\vert >1}$) and $c_{1}=0$, and the boundary condition $P(0)=1$ requires that $c_{0}=1$.

Finally, we note that reaching position -1 from position $n$, the required condition for halting, is the same as reaching position 0 from position $n+1$, so we must increment $n$.

For these reasons, Hydra is considered to be a probviously nonhalting machine.