Antihydra: Difference between revisions

Revision as of 03:32, 17 February 2025

Unsolved problem:

Does Antihydra run forever?

Artistic depiction of Antihydra by Jadeix

Antihydra (1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA (bbch)) is a probviously nonhalting BB(6) Collatz-like Cryptid. In fact, it was the first identified BB(6) Cryptid. It is closely related to Hydra.

It simulates iterations of the Collatz-like Hydra function:

H(n)=\left\lfloor {\frac {3n}{2}}\right\rfloor ={\begin{cases}{\frac {3n}{2}}&{\text{if }}n{\text{ even}}\\{\frac {3n-1}{2}}&{\text{if }}n{\text{ odd}}\\\end{cases}}

starting from 8:

8\to 12\to 18\to 27\to 40\to 60\to 90\to 135\to 202\cdots

Antihydra halts if and only if the cumulative number of odd values in this sequence is ever more than twice the cumulative number of even values.

If we treat the parity of successive values in this sequence as independent random coin flips, then this is a biased random walk and has a miniscule chance of ever halting, thus we say that this TM "probviously" does not halt. But proving this would require solving a Collatz-like problem.

Turing Machine

Antihydra is the TM 1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA (bbch)

Antihydra
	0	1
A	1RB	1RA
B	0LC	1LE
C	1LD	1LC
D	1LA	0LB
E	1LF	1RE
F	---	0RA

It was discovered by @mxdys on 28 Jun 2024 and shared on Discord^[1] and Racheline discovered that it iterates the Hydra function.

Analysis

Let $A(a+4,b)=0^{\infty }\;1^{b}\;0\;1^{a}\;E>\;0^{\infty }$ , then^[2]

{\begin{array}{l}{\text{Start}}&&\to &A(8,&0)\\A(2a,&b)&\to &A(3a,&b+2)\\A(2a+1,&b)&\to &A(3a+1,&b-1)&{\text{if}}&b>0\\A(2a+1,&0)&\to &{\text{HALT}}\end{array}}

At each iteration,

a\mapsto H(a)

and

b\mapsto {\begin{cases}b+2&{\text{if }}a{\text{ is even}}\\b-1&{\text{if }}a{\text{ is odd}}\\\end{cases}}

halting iff b ever reaches -1.

Biased Random Walk

If we consider the sequence of parities of $a$ to be independent random coin flips, then the movement of $b$ is a biased random walk (50% chance of +2, 50% of -1). Starting from $b=n$ , the chance of such a random walk ever reaching $b=-1$ is $\left({\frac {1}{2}}\right)^{n+1}$ and the expected value of b after k steps is ${\frac {k}{2}}$ .

Simulation

@mxdys has simulated this iteration out to $2^{31}=2\,147\,483\,648$ steps at which point $b=1\,073\,720\,884$ (Discord link), this is 20940 (0.002%) below the expected value if this were a random walk. If this was a random walk, the chance of ever halting from this point is

\left({\frac {1}{2}}\right)^{1\,073\,720\,885}

an extremely miniscule chance.

Sources

↑ Discord message, accessed 30 June 2024.
↑ S. Ligocki, "BB(6) is Hard (Antihydra)" (2024). Accessed 22 July 2024.

[1] Discord message, accessed 30 June 2024.

[2] S. Ligocki, "BB(6) is Hard (Antihydra)" (2024). Accessed 22 July 2024.

[1]

[2]

@@ Line 1: / Line 1: @@
-{{machine|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA}}{{unsolved|Does Antihydra run forever?}}{{TM|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA|undecided}}
+{{machine|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA}}{{unsolved|Does Antihydra run forever?}}
 [[File:Antihydra-depiction.png|right|thumb|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
+'''Antihydra''' ({{TM|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA|undecided}}) is a [[probviously]] nonhalting [[BB(6)]] [[Collatz-like]] [[Cryptid]]. In fact, it was the first identified BB(6) Cryptid. It is closely related to [[Hydra]].
-<math display="block">H_{n+1}=\bigg\lfloor\frac{3}{2}H_n\bigg\rfloor,H_0=8,</math>
-ever has a cumulative count of odd terms that surpasses twice the cumulative count of even terms.
+It simulates iterations of the Collatz-like [[Hydra function]]:
+<math display="block">H(n) = \left\lfloor \frac{3n}{2} \right\rfloor = \begin{cases}
+  \frac{3n}{2}     & \text{if } n \text{ even} \\
+  \frac{3n-1}{2}  & \text{if } n \text{ odd} \\
+\end{cases}</math>starting from 8:
+<math display="block">8 \to 12 \to 18 \to 27 \to 40 \to 60 \to 90 \to 135 \to 202 \cdots</math>
+Antihydra halts if and only if the cumulative number of odd values in this sequence is ever more than twice the cumulative number of even values.
+If we treat the parity of successive values in this sequence as independent random coin flips, then this is a biased random walk and has a miniscule chance of ever halting, thus we say that this TM "probviously" does not halt. But proving this would require solving a Collatz-like problem.
+== Turing Machine ==
+Antihydra is the TM {{TM|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA|undecided}}
+{| class="wikitable"
+|+Antihydra
+!
+!0
+!1
+|-
+!'''A'''
+|1RB
+|1RA
+|-
+!'''B'''
+|0LC
+|1LE
+|-
+!'''C'''
+|1LD
+|1LC
+|-
+!'''D'''
+|1LA
+|0LB
+|-
+!'''E'''
+|1LF
+|1RE
+|-
+!'''F'''
+| ---
+|0RA
+|}
+It was discovered by @mxdys on 28 Jun 2024 and shared on Discord<ref>[https://discord.com/channels/960643023006490684/1026577255754903572/1256223215206924318 Discord message], accessed 30 June 2024.</ref> and Racheline discovered that it iterates the Hydra function.
 == Analysis ==
-===Rules===
+Let <math>A(a+4, b) = 0^\infty \; 1^b \; 0 \; 1^a \; E> \; 0^\infty</math>, then<ref>S. Ligocki, "[https://www.sligocki.com/2024/07/06/bb-6-2-is-hard.html BB(6) is Hard (Antihydra)]" (2024). Accessed 22 July 2024.</ref>
-Let <math>A(a,b):=0^\infty\;1^a\;0\;1^b\;\textrm{E>}\;0^\infty</math>. Then<ref name="bl">S. Ligocki, "[https://www.sligocki.com/2024/07/06/bb-6-2-is-hard.html BB(6) is Hard (Antihydra)]" (2024). Accessed 22 July 2024.</ref>,
-<math display="block">\begin{array}{|lll|}\hline
+<math display="block">\begin{array}{l}
-A(a,2b)& \xrightarrow{2a+3b^2+12b+11}& A(a+2,3b+2),\\
+  \text{Start}&& \to & A(8,    & 0) \\
-A(0,2b+1)&\xrightarrow{3b^2+9b-1}& 0^\infty\;\textrm{<F}\;110\;1^{3b}\;0^\infty,\\
+  A(2a,   & b) & \to & A(3a,   & b+2) \\
-A(a+1,2b+1)&\xrightarrow{3b^2+12b+5}& A(a,3b+3).\\\hline
+  A(2a+1, & b) & \to & A(3a+1, & b-1) & \text{if} & b>0 \\
-\end{array}</math>
+  A(2a+1, & 0) & \to & \text{HALT}
-===Proof===
+\end{array}</math>At each iteration, <math>a \mapsto H(a)</math> and
-Consider the partial configuration <math>P(m,n):=0\;1^m\;\textrm{E>}\;0\;1^n\;0^\infty</math>. The configuration after two steps is <math>0\;1^{m-1}\;0\;\textrm{A>}\;1^{n+1}\;0^\infty</math>. We note the following shift rule:
-<math display="block">\begin{array}{|c|}\hline\textrm{A>}\;1^s\xrightarrow{s}1^s\;\textrm{A>}\\\hline\end{array}</math>
+<math display="block">b \mapsto \begin{cases}
-As a result, we get <math>0\;1^{m-1}\;0\;1^{n+1}\;\textrm{A>}\;0^\infty</math> after <math>n+1</math> steps. Advancing two steps produces <math>0\;1^{m-1}\;0\;1^{n+2}\;\textrm{<C}\;0^\infty</math>. A second shift rule is useful here:
+  b+2    & \text{if } a \text{ is even} \\
-<math display="block">\begin{array}{|c|}\hline1^s\;\textrm{<C}\xrightarrow{s}\textrm{<C}\;1^s\\\hline\end{array}</math>
+  b-1    & \text{if } a \text{ is odd} \\
-This allows us to reach <math>0\;1^{m-1}\;0\;\textrm{<C}\;1^{n+2}\;0^\infty</math> in <math>n+2</math> steps. Moving five more steps gets us to <math>0\;1^{m-2}\;\textrm{E>}\;0\;1^{n+3}\;0^\infty</math>, which is the same configuration as <math>P(m-2,n+3)</math>. Accounting for the head movement creates the condition that <math>m\ge 4</math>. In summary:
+\end{cases}</math>
-<math display="block">\begin{array}{|c|}\hline P(m,n)\xrightarrow{2n+12}P(m-2,n+3)\text{ if }m\ge 4.\\\hline\end{array}</math>
-With <math>A(a,b)</math> we have <math>P(b,0)</math>. As a result, we can apply this rule <math display="inline>\big\lfloor\frac{1}{2}b\big\rfloor-1</math> times (assuming <math>b\ge 4</math>), which creates two possible scenarios:
+halting iff b ever reaches -1.
-#If <math>b\equiv0\ (\operatorname{mod}2)</math>, then in <math>\sum_{i=0}^{(b/2)-2}(2\times 3i+12)=\textstyle\frac{3}{4}b^2+\frac{3}{2}b-6</math> steps we arrive at <math display="inline">P\Big(2,\frac{3}{2}b-3\Big)</math>. The matching complete configuration is <math>0^\infty\;1^a\;011\;\textrm{E>}\;0\;1^{(3b)/2-3}\;0^\infty</math>. After <math>3b+4</math> steps this becomes <math>0^\infty\;1^a\;\textrm{<C}\;00\;1^{(3b)/2}\;0^\infty</math>, which then leads to <math>0^\infty\;\textrm{<C}\;1^a\;00\;1^{(3b)/2}\;0^\infty</math> in <math>a</math> steps. After five more steps, we reach <math>0^\infty\;1\;\textrm{E>}\;1^{a+2}\;00\;1^{(3b)/2}\;0^\infty</math>, from which another shift rule must be applied:<math display="block">\begin{array}{|c|}\hline\textrm{E>}\;1^s\xrightarrow{s}1^s\;\textrm{E>}\\\hline\end{array}</math>Doing so allows us to get the configuration <math>0^\infty\;1^{a+3}\;\textrm{E>}\;00\;1^{(3b)/2}\;0^\infty</math> in <math>a+2</math> steps. In six steps we have <math>0^\infty\;1^{a+2}\;011\;\textrm{E>}\;1^{(3b)/2}\;0^\infty</math>, so we use the shift rule again, ending at <math>0^\infty\;1^{a+2}\;0\;1^{(3b)/2+2}\;\textrm{E>}\;0^\infty</math>, equal to <math display="inline">A\Big(a+2,\frac{3}{2}b+2\Big)</math>, <math display="inline">\frac{3}{2}b</math> steps later. This gives a total of <math display="inline">2a+\frac{3}{4}b^2+6b+11</math> steps.
-#If <math>b\equiv1\ (\operatorname{mod}2)</math>, then in <math display="inline">\frac{3}{4}b^2-\frac{27}{4}</math> steps we arrive at <math display="inline">P\Big(3,\frac{3b-9}{2}\Big)</math>. The matching complete configuration is <math>0^\infty\;1^a\;0111\;\textrm{E>}\;0\;1^{(3b-9)/2}\;0^\infty</math>. After <math>3b+2</math> steps this becomes <math>0^\infty\;1^a\;\textrm{<F}\;110\;1^{(3b-3)/2}\;0^\infty</math>. If <math>a=0</math> then we have reached the undefined <code>F0</code> transition with a total of <math display="inline">\frac{3}{4}b^2+3b-\frac{19}{4}</math> steps. Otherwise, continuing for six steps gives us <math>0^\infty\;1^{a-1}\;0111\;\textrm{E>}\;1^{(3b-3)/2}\;0^\infty</math>. We conclude with the configuration <math>0^\infty\;1^{a-1}\;0\;1^{(3b+3)/2}\;\textrm{E>}\;0^\infty</math>, equal to <math display="inline">A\Big(a-1,\frac{3b+3}{2}\Big)</math>, in <math display="inline">\frac{3b-3}{2}</math> steps. This gives a total of <math display="inline">\frac{3}{4}b^2+\frac{9}{2}b-\frac{1}{4}</math> steps.
+== Biased Random Walk ==
-The information above can be summarized as
+If we consider the sequence of parities of <math>a</math> to be independent random coin flips, then the movement of <math>b</math> is a biased random walk (50% chance of +2, 50% of -1). Starting from <math>b = n</math>, the chance of such a random walk ever reaching <math>b = -1</math> is <math>\left(\frac{1}{2}\right)^{n+1}</math> and the expected value of b after k steps is <math>\frac{k}{2}</math>.
-<math display="block">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}</math>
-Substituting <math>b\leftarrow 2b</math> for the first case and <math>b\leftarrow 2b+1</math> for the other two yields the final result.
+== Simulation ==
-== Trajectory ==
+@mxdys has simulated this iteration out to <math>2^{31} = 2\,147\,483\,648</math> steps at which point <math>b = 1\,073\,720\,884</math> ([https://discord.com/channels/960643023006490684/1026577255754903572/1258509066196746351 Discord link]), this is 20940 (0.002%) below the expected value if this were a random walk. If this was a random walk, the chance of ever halting from this point is
-steps are required to enter the configuration <math>A(0, 4)</math> before the [[Collatz-like]] rules are repeatedly applied. Here are the first few iterations:
-[[File:AHydra 0-419.gif|right|thumb|Animation of the blank tape becoming <math>A(6,23)</math> in 419 steps (''[https://wiki.bbchallenge.org/w/images/3/36/AHydra_0-419.gif click to view]'').]]
+<math display="block">\left(\frac{1}{2}\right)^{1\,073\,720\,885}</math>
-<math display="block">\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}</math>
-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 <math>2^{31}</math> rule steps, we have <math>b=1073720884</math><ref name="bl"></ref>, so this machine, if treated as a random process, has an extremely minuscule chance of ever halting.
+an extremely miniscule chance.
-==References==
+==Sources==
+<references />
 [[Category:Individual machines]]
 [[Category:Cryptids]]