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 ${\textstyle H(n)={\Big \lfloor }{\frac {3}{2}}n{\Big \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 ${\textstyle {\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 ${\textstyle H(n)={\Big \lfloor }{\frac {3}{2}}n{\Big \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^{\infty }\;1^{a}\;0\;1^{b}\;{\textrm {E>}}\;0^{\infty }$. Then,

$${\begin{array}{|lll|}\hline A(a,2b)&\xrightarrow {2a+3b^{2}+12b+11} &A(a+2,3b+2),\\A(0,2b+1)&\xrightarrow {3b^{2}+9b-1} &0^{\infty }\;{\textrm {<F}}\;110\;1^{3b}\;0^{\infty },\\A(a+1,2b+1)&\xrightarrow {3b^{2}+12b+5} &A(a,3b+3).\\\hline \end{array}}$$

Proof

Consider the partial configuration $P(m,n):=0\;1^{m}\;{\textrm {E>}}\;0\;1^{n}\;0^{\infty }$. The configuration after two steps is $0\;1^{m-1}\;0\;{\textrm {A>}}\;1^{n+1}\;0^{\infty }$. We note the following shift rule:

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

As a result, we get $0\;1^{m-1}\;0\;1^{n+1}\;{\textrm {A>}}\;0^{\infty }$ after $n+1$ steps. Advancing two steps produces $0\;1^{m-1}\;0\;1^{n+2}\;{\textrm {<C}}\;0^{\infty }$. A second shift rule is useful here:

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

This allows us to reach $0\;1^{m-1}\;0\;{\textrm {<C}}\;1^{n+2}\;0^{\infty }$ in $n+2$ steps. Moving five more steps gets us to $0\;1^{m-2}\;{\textrm {E>}}\;0\;1^{n+3}\;0^{\infty }$, which is the same configuration as $P(m-2,n+3)$. Accounting for the head movement creates the condition that $m\geq 4$. In summary:

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

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

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

The information above can be summarized as

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

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|}\hline A(0,4)\xrightarrow {47} A(2,8)\xrightarrow {111} A(4,14)\xrightarrow {250} A(6,23)\xrightarrow {500} A(5,36)\xrightarrow {1209} A(7,56)\xrightarrow {2713} A(9,86)\rightarrow \cdots \\\hline \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 ${\textstyle P(n)={\frac {1}{2}}P(n-1)+{\frac {1}{2}}P(n+2)}$. Solutions to this recurrence relation come in the form ${\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}}$, which after applying the appropriate boundary conditions reduces to ${\textstyle 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 ${\textstyle {\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 ${\textstyle {\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.