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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} s and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} consecutive Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} s, separated by a single Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} . It does this by "borrowing" a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} from the right side and, through a series of back-and-forth head movements, "moves" this Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0} toward the one separating Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \frac{3}{2}} times as many Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} s on the tape when the distance has been closed. After that, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} are updated. If the previous value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} was even, then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} becomes $y+2$. Otherwise, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} becomes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y-1} or Antihydra halts if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} was 0.

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle H(n)=\Big\lfloor\frac{3}{2}n\Big\rfloor} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_k} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b_k} be integer sequences defined below: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{array}{l} a_0=0,&a_{k+1} = \begin{cases}a_k + 2 & \text{if } b_k\equiv0\pmod{2}\\a_k - 1 & \text{if }b_k\equiv1\pmod{2} \\\end{cases},&b_0=8,&b_{k+1}=H(b_k).\end{array}} Antihydra halts if and only if there exists any number $i$ for which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.

Analysis

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A(a,b):=0^\infty\;1^a\;0\;1^b\;\textrm{E>}\;0^\infty} . Then, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(m,n):=0\;1^m\;\textrm{E>}\;0\;1^n\;0^\infty} . The configuration after two steps is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} steps. After five more steps, we reach Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0^\infty\;1\;\textrm{E>}\;1^{a+2}\;00\;1^{(3b)/2}\;0^\infty} , from which another shift rule must be applied:Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0^\infty\;1^{a+3}\;\textrm{E>}\;00\;1^{(3b)/2}\;0^\infty} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a+2} steps. In six steps we have Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0^\infty\;1^{a+2}\;011\;\textrm{E>}\;1^{(3b)/2}\;0^\infty} , so we use the shift rule again, ending at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0^\infty\;1^{a+2}\;0\;1^{(3b)/2+2}\;\textrm{E>}\;0^\infty} , equal to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle A\Big(a+2,\frac{3}{2}b+2\Big)} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \frac{3}{2}b} steps later. This gives a total of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle 2a+\frac{3}{4}b^2+6b+11} steps.
2. If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b\equiv1\ (\operatorname{mod}2)} , then in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \frac{3}{4}b^2-\frac{27}{4}} steps we arrive at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle P\Big(3,\frac{3b-9}{2}\Big)} . The matching complete configuration is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0^\infty\;1^a\;0111\;\textrm{E>}\;0\;1^{(3b-9)/2}\;0^\infty} . After Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3b+2} steps this becomes Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0^\infty\;1^a\;\textrm{<F}\;110\;1^{(3b-3)/2}\;0^\infty} . If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a=0} then we have reached the undefined F0 transition with a total of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \frac{3}{4}b^2+3b-\frac{19}{4}} steps. Otherwise, continuing for six steps gives us Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0^\infty\;1^{a-1}\;0111\;\textrm{E>}\;1^{(3b-3)/2}\;0^\infty} . We conclude with the configuration Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0^\infty\;1^{a-1}\;0\;1^{(3b+3)/2}\;\textrm{E>}\;0^\infty} , equal to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle A\Big(a-1,\frac{3b+3}{2}\Big)} , in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \frac{3b-3}{2}} steps. This gives a total of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \frac{3}{4}b^2+\frac{9}{2}b-\frac{1}{4}} steps.

The information above can be summarized as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A(a,b)\rightarrow\begin{cases}A\Big(a+2,\frac{3}{2}b+2\Big)&\text{if }b\ge 2,b\equiv0\pmod{2};\\0^\infty\;\textrm{<F}\;110\;1^{(3b-3)/2}\;0^\infty&\text{if }b\ge3,b\equiv1\pmod{2},\text{ and }a=0;\\A\Big(a-1,\frac{3b+3}{2}\Big)&\text{if }b\ge3,b\equiv1\pmod{2},\text{ and }a>0.\end{cases}} Substituting Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b\leftarrow 2b} for the first case and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A(0, 4)} before the rules are repeatedly applied. So far, Antihydra has been simulated to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{31}} rule steps, at which point Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b=1073720884} . Here are the first few: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(n)} is the probability that the walker will reach position -1 from position Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , then it can be seen that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle P(n)=\frac{1}{2}P(n-1)+\frac{1}{2}P(n+2)} . Solutions to this recurrence relation come in the form Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} steps is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle \frac{1}{2}k} strongly suggests Antihydra will not halt.

To view an animation of the blank tape becoming Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A(6,23)} in 419 steps, click here.