Antihydra

Unsolved problem:

Does Antihydra run forever?

1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA (bbch)

Artistic depiction of Antihydra by Jadeix

Antihydra is the first BB(6) Cryptid to be identified. It operates by repeatedly applying the function $H(n)=\lfloor \frac{3}{2}n\rfloor$, starting with $n=8$. Determining whether this Turing machine halts requires solving a Collatz-like mathematical problem. Specifically, one must establish a significant result regarding the frequency of odd versus even numbers generated throughout the sequence. While probabilistic arguments based on random walks suggest Antihydra probviously runs indefinitely, proving this remains challenging. The difficulty stems from both the lack of an exploitable pattern in the sequence’s parities and the inherent complexity of Collatz-like problems.

Description

The transition table of Antihydra.

Antihydra basically repeatedly modifies the integer ordered pair $(x,y)$ starting at $(0,4)$, which is represented on the tape as $x$ consecutive $1$s and $y$ consecutive $1$s, separated by a single $0$. It does this by "borrowing" a $0$ from the right side and, through a series of back-and-forth head movements, "moves" this $0$ toward the one separating $x$ and $y$, two units at a time. As this happens, the head visits new cells on the right, which has the effect of there being about $\frac{3}{2}$ times as many $1$s on the tape when the distance has been closed. After that, $x$ and $y$ are updated. If the previous value of $x$ was even, then $y$ becomes $y+2$. Otherwise, $y$ becomes $y-1$ or Antihydra halts if $y$ was 0.

To resolve the halting problem for Antihydra, one must determine if, given the function $H(n)=\lfloor \frac{3}{2}n\rfloor$, the sequence of iterates $(8,H(8),H^2(8),H^3(8),H^4(8),\cdots )$ could ever produce a cumulative quantity of odd numbers that is more than twice that of the even numbers.

Attributions

Antihydra and its pseudo-random behaviour were reported on Discord by mxdys on 28 June 2024, and Racheline discovered the high-level rules soon after, where it was found to be closely related to Hydra.

Analysis

Let $A(a,b):=0^{\mathrm{\infty }}{1}^{a}01^b\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$. Then, $$\begin{array}{lll}A(a,2b)& \stackrel{2a+3b^2+12b+11}{\to }& A(a+2,3b+2),\\ A(0,2b+1)& \stackrel{3b^2+9b-1}{\to }& 0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>F</mrow>}1101^{3b}{0}^{\mathrm{\infty }},\\ A(a+1,2b+1)& \stackrel{3b^2+12b+5}{\to }& A(a,3b+3).\end{array}$$

Proof

Consider the partial configuration $P(m,n):=01^m\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}01^n{0}^{\mathrm{\infty }}$. The configuration after two steps is $01^{m-1}0\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{1}^{n+1}{0}^{\mathrm{\infty }}$. We note the following shift rule: $$\begin{array}{c}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{1}^s\stackrel{s}{\to }{1}^s\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}\end{array}$$ As a result, we get $01^{m-1}01^{n+1}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$ after $n+1$ steps. Advancing two steps produces $01^{m-1}01^{n+2}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{0}^{\mathrm{\infty }}$. A second shift rule is useful here: $$\begin{array}{c}{1}^s\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}\stackrel{s}{\to }\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^s\end{array}$$ This allows us to reach $01^{m-1}0\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{n+2}{0}^{\mathrm{\infty }}$ in $n+2$ steps. Moving five more steps gets us to $01^{m-2}\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}01^{n+3}{0}^{\mathrm{\infty }}$, which is the same configuration as $P(m-2,n+3)$. Accounting for the head movement creates the condition that $m\ge 4$. In summary: $$\begin{array}{c}P(m,n)\stackrel{2n+12}{\to }P(m-2,n+3)\text{ if }m\ge 4.\end{array}$$ With $A(a,b)$ we have $P(b,0)$. As a result, we can apply this rule $\lfloor \frac{1}{2}b\rfloor -1$ times (assuming $b\ge 4$), which creates two possible scenarios:

1. If $b\equiv 0(\mathrm{mod}2)$, then in $\sum _{i=0}^{(b/2)-2}(2\times 3i+12)=\frac{3}{4}{b}^2+\frac{3}{2}b-6$ steps we arrive at $P(2,\frac{3}{2}b-3)$. The matching complete configuration is $0^{\mathrm{\infty }}{1}^{a}011\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}01^{(3b)/2-3}{0}^{\mathrm{\infty }}$. After $3b+4$ steps this becomes $0^{\mathrm{\infty }}{1}^a\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}001^{(3b)/2}{0}^{\mathrm{\infty }}$, which then leads to $0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>C</mrow>}{1}^{a}001^{(3b)/2}{0}^{\mathrm{\infty }}$ in $a$ steps. After five more steps, we reach $0^{\mathrm{\infty }}1\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{1}^{a+2}001^{(3b)/2}{0}^{\mathrm{\infty }}$, from which another shift rule must be applied:$$\begin{array}{c}\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{1}^s\stackrel{s}{\to }{1}^s\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}\end{array}$$Doing so allows us to get the configuration $0^{\mathrm{\infty }}{1}^{a+3}\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}001^{(3b)/2}{0}^{\mathrm{\infty }}$ in $a+2$ steps. In six steps we have $0^{\mathrm{\infty }}{1}^{a+2}011\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{1}^{(3b)/2}{0}^{\mathrm{\infty }}$, so we use the shift rule again, ending at $0^{\mathrm{\infty }}{1}^{a+2}01^{(3b)/2+2}\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, equal to $A(a+2,\frac{3}{2}b+2)$, $\frac{3}{2}b$ steps later. This gives a total of $2a+\frac{3}{4}{b}^2+6b+11$ steps.
2. If $b\equiv 1(\mathrm{mod}2)$, then in $\frac{3}{4}{b}^2-\frac{27}{4}$ steps we arrive at $P(3,\frac{3b-9}{2})$. The matching complete configuration is $0^{\mathrm{\infty }}{1}^{a}0111\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}01^{(3b-9)/2}{0}^{\mathrm{\infty }}$. After $3b+2$ steps this becomes $0^{\mathrm{\infty }}{1}^a\text{<mrow data-mjx-texclass="ORD"><mo><</mo>F</mrow>}1101^{(3b-3)/2}{0}^{\mathrm{\infty }}$. If $a=0$ then we have reached the undefined F0 transition with a total of $\frac{3}{4}{b}^2+3b-\frac{19}{4}$ steps. Otherwise, continuing for six steps gives us $0^{\mathrm{\infty }}{1}^{a-1}0111\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{1}^{(3b-3)/2}{0}^{\mathrm{\infty }}$. We conclude with the configuration $0^{\mathrm{\infty }}{1}^{a-1}01^{(3b+3)/2}\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$, equal to $A(a-1,\frac{3b+3}{2})$, in $\frac{3b-3}{2}$ steps. This gives a total of $\frac{3}{4}{b}^2+\frac{9}{2}b-\frac{1}{4}$ steps.

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

Trajectory

11 steps are required to enter the configuration $A(0,4)$ before the rules are repeatedly applied. So far, Antihydra has been simulated to $2^{31}$ rule steps, at which point $b=1073720884$. Here are the first few: $$\begin{array}{c}A(0,4)\stackrel{47}{\to }A(2,8)\stackrel{111}{\to }A(4,14)\stackrel{250}{\to }A(6,23)\stackrel{500}{\to }A(5,36)\stackrel{1209}{\to }A(7,56)\stackrel{2713}{\to }A(9,86)\to \cdots \end{array}$$

A heuristic nonhalting argument

A binary representation of the first 1000 steps of the evolution of the exponentially increasing variable of the Antihydra iteration (a = a + a//2). The colored background indicates whether the value is even or odd with blue and red, respectively.

The trajectory of $b$ values can be approximated by a random walk in which the walker can only move in step sizes +2 or -1 with equal probability, starting at position 0. If $P(n)$ is the probability that the walker will reach position -1 from position $n$, then it can be seen that $P(n)=\frac{1}{2}P(n-1)+\frac{1}{2}P(n+2)$. Solutions to this recurrence relation come in the form $P(n)=c_0{\left(\frac{\sqrt{5}-1}{2}\right)}^n+c_1+c_2{(-\frac{1+\sqrt{5}}{2})}^n$, which after applying the appropriate boundary conditions reduces to $P(n)={\left(\frac{\sqrt{5}-1}{2}\right)}^{n+1}$. This means that if walker were to get to position 1073720884 then the probability of it ever reaching position -1 is ${\left(\frac{\sqrt{5}-1}{2}\right)}^{1073720885}\approx 4.841\times 10^{-224394395}$. This combined with the fact that the expected position of the walker after $k$ steps is $\frac{1}{2}k$ strongly suggests Antihydra will not halt.

To view an animation of the blank tape becoming $A(6,23)$ in 419 steps, click here.