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 the Collatz-like mathematical problem of whether there eventually exists a step at which $H(n)$ has been applied to (strictly) more than twice as many odd as even numbers. Proving a result remains challenging due to the lack of an exploitable pattern in the sequence's parities, although probabilistic arguments based on random walks suggest Antihydra has a minuscule chance of halting.

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.

Let $H(n)=\lfloor \frac{3}{2}n\rfloor$, and $a_k$ and $b_k$ be integer sequences defined below: $$\begin{array}{llll}{a}_0=0,& a_{k+1}=\{\begin{array}{ll}{a}_k+2& \text{if }{b}_k\equiv 0(\mathrm{mod}2)\\ a_k-1& \text{if }{b}_k\equiv 1(\mathrm{mod}2)\\ \end{array},& b_0=8,& b_{k+1}=H(b_k).\end{array}$$ Antihydra halts if and only if there exists any number $i$ for which $a_i<0$.

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. The "anti-" in the name is due to the fact that the roles of even and odd numbers are switched compared to the behavior of 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 is $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.

The page Hydra function shows how these rules can be simplified to use that function instead, along with Hydra.

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 the 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 probviously runs indefinitely.

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

Code

The following Python programs implement the abstracted behavior of the Antihydra. Proving whether they halt or not would also solve the Antihydra problem:

# Keeps track of how many odd and even numbers have been encountered
a = 0
# The iterated value
b = 8
# If a < 0 there have been (strictly) more than twice as many odd as even numbers and the program halts
while a != -1:
    # If b is even, add 2 to b so even numbers count twice
    if b % 2 == 0:
        a += 2
    else:
        a -= 1
    # Add the number divided by two (integer division, rounding down) to itself
    b += b//2

Integer division by two is equivalent to shifting the binary representation of the number one place to the right (discarding the least significant bit). Codegolfed versions by mxdys:

a,b=0,8
while a!=-1:
    a+=2-b%2*3
    b+=b>>1

even shorter, here the order of the two sequential operations (shifted addition, even/odd counting) is reversed:

a,b=3,8
while a:b+=b>>1;a+=2-b%2*3