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}=\lfloor \frac{3}{2}{H}_n\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^{\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 another $\frac{3a+1}{2}$ 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. Here are the first few iterations:

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

$$\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)\to \cdots \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 $\frac{1}{2}k$, and it can be shown that the probability of the walker reaching position -1 from position $n$ is ${\left(\frac{\sqrt{5}-1}{2}\right)}^{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 $\frac{1}{2}$ or first moving -1 with probability $\frac{1}{2}$. Therefore, the recurrence relation is $$P(n)=\frac{1}{2}P(n+2)+\frac{1}{2}P(n-1)\text{ for }n\ge 1.$$ Bringing all terms with $P$ to the left side of the equation and then substituting $n\leftarrow n+1$ gives $$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 $f(z)=-\frac{1}{2}+z-\frac{1}{2}{z}^3$, whose zeroes are given by $$z_0=\frac{\sqrt{5}-1}{2},z_1=1,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, $$P(n)=c_0{\left(\frac{\sqrt{5}-1}{2}\right)}^n+c_1+c_2{(-\frac{1+\sqrt{5}}{2})}^n$$ The boundary condition $\underset{n\to \mathrm{\infty }}{\lim }P(n)=0$ means $c_2=0$ (since $|-\frac{1+\sqrt{5}}{2}|>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.