Antihydra

Unsolved problem:

Does Antihydra run forever?

1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA (bbch)

Antihydra is a BB(6) Cryptid. Its pseudo-random behaviour was first reported on Discord by mxdys on 28 June 2024, and Racheline discovered the high-level rules soon after. It was named after the 2-state, 5-symbol Turing machine called Hydra for sharing many similarities to it.

Antihydra is known to not generate Sturmian words (Corollary 4).

Artistic depiction of Antihydra by Jadeix

0 1 A 1RB 1RA B 0LC 1LE C 1LD 1LC D 1LA 0LB E 1LF 1RE F --- 0RA The transition table of Antihydra.

A community trophy - to be awarded to the first person or group who solves the Antihydra problem

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 is $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.

In effect, the halting problem for Antihydra is about whether repeatedly applying the function ${\textstyle f(n)={\Big \lfloor }{\frac {3n}{2}}{\Big \rfloor }+2}$ will at some point produce more odd values of $n$ than twice the number of even values.

These rules can be modified to use the function ${\textstyle H(n)={\Big \lfloor }{\frac {3n}{2}}{\Big \rfloor }}$, or the Hydra function, which strengthens Antihydra's similarities to 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|}\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}}$$

The trajectory of $b$ values resembles 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 the 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 probviously runs indefinitely.

Code

The following Python program implements the abstracted behavior of the Antihydra. Proving whether it halts or not would also solve the Antihydra problem:

# Current value of the iterated Hydra function starting with initial value 8
h = 8
# (Collatz-like) condition counter that keeps track of how many odd and even numbers have been encountered
c = 0
# If c equals -1 there have been (strictly) more than twice as many odd as even numbers and the program halts
while c != -1:
    # If h is even, add 2 to c so even numbers count twice
    if h % 2 == 0:
        c += 2
    else:
        c -= 1
    # Add the current hydra value divided by two (integer division, rounding down) to itself (Hydra function)
    # Note that integer division by 2 is equivalent to one bit shift to the right (h >> 1)
    h += h//2

Fast Hydra/Antihydra simulation code by Greg Kuperberg (who said it could be made faster using FLINT):

# Python script to demonstrate almost linear time hydra simulation
# using fast multiplication. 
# by Greg Kuperberg

import time
from gmpy2 import mpz,bit_mask

# Straight computation of t steps of hydra
def simple(n,t):
    for s in range(t): n += n>>1
    return n

# Accelerated computation of 2**e steps of hydra
def hydra(n,e):
    if e < 9: return simple(n,1<<e)
    t = 1<<(e-1)
    (p3t,m) = (mpz(3)**t,bit_mask(t))
    n = p3t*(n>>t) + hydra(n&m,e-1)
    return p3t*(n>>t) + hydra(n&m,e-1)

def elapsed():
    (last,elapsed.mark) = (elapsed.mark,time.process_time())
    return elapsed.mark-last
elapsed.mark = 0

(n,e) = (mpz(3),25)

elapsed()
print('hydra:  steps=%d hash=%016x time=%.6fs'
    % (1<<e,hash(hydra(n,e)),elapsed()))

# Quadratic time algorithm for comparison
# print('simple: steps=%d hash=%016x time=%.6fs'
#     % (1<<e,hash(simple(n,1<<e)),elapsed()))