Antihydra

Unsolved problem:

Does Antihydra run forever?

1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA (bbch)

Artistic depiction of Antihydra by Jadeix

Antihydra is a BB(6) Cryptid. It is similar to Hydra in that it halts if and only if the sequence

$$H_{n+1}={\bigg \lfloor }{\frac {3}{2}}H_{n}{\bigg \rfloor },H_{0}=8,$$

ever has a cumulative count of odd terms that surpasses twice the cumulative count of even terms.

Analysis

Rules

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 Collatz-like rules are repeatedly applied. Here are the first few iterations:

Animation of the blank tape becoming $A(6,23)$ in 419 steps (click to view).

$${\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)\rightarrow \cdots \\\hline \end{array}}$$

The halting problems for Antihydra and Hydra are connected by the Hydra function, so the heuristic argument that suggests Hydra is probviously nonhalting can be applied here. After $2^{31}$ rule steps, we have $b=1073720884$, so this machine, if treated as a random process, has an extremely minuscule chance of ever halting.