|
|
| Line 1: |
Line 1: |
| {{machine|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA}}{{unsolved|Does Hydra run forever?}}{{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA|undecided}} | | {{machine|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA}}{{unsolved|Does Hydra run forever?}}{{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA|undecided}} |
| '''Hydra''' is a [[BB(2,5)]] [[Cryptid]]. It simulates computing the terms of the sequence | | '''Hydra''' is a [[BB(2,5)]] machine that simulates the [[Collatz-like]] iteration |
| <math display="block>H_{n+1}=\bigg\lfloor\frac{3}{2}H_n\bigg\rfloor,H_0=3,</math> | | |
| halting if and only if there exists a point in the sequence where the number of even terms up to that point exceeds twice the number of odd terms.
| | <math display="block">\begin{array}{l} |
| == Analysis ==
| | C(2a+1, & b) & \to & A(3a+1, & b+2) \\ |
| ===Rules===
| | C(2a, & b) & \to & A(3a, & b-1) & \text{if} & b>0 \\ |
| Let <math>C(a,b):=0^\infty\;\textrm{<A}\;2\;0^a\;3^b\;2\;0^\infty</math>. Then<ref>S. Ligocki, "[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)] (2024). Accessed 22 July 2024.</ref>,
| | C(2a, & 0) & \to & \text{HALT} |
| <math display="block">\begin{array}{|lll|}\hline
| |
| C(2a,0)&\xrightarrow{6a^2+20a+4}&0^\infty\;3^{3a+1}\;1\;\textrm{A>}\;2\;0^\infty,\\ | |
| C(2a,b+1)&\xrightarrow{6a^2+23a+10}&C(3a+3,b),\\
| |
| C(2a+1,b)&\xrightarrow{4b+6a^2+23a+26}&C(3a+3,b+2).\\\hline | |
| \end{array}</math> | | \end{array}</math> |
| By scaling and translating these rules we acquire the [[Hydra function]] that relates it to [[Antihydra]]<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>.
| | <br> |
| ===Proof===
| | starting from <math>C(3,0)</math>, using configurations of the form <math>C(a+2,b) = 0^\infty \; <B \; 0^{3a} \; 3^b \; 2 \; 0^\infty</math>.<ref>S. Ligocki, "[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)] (2024). Accessed 22 July 2024.</ref> |
| Consider the partial configuration <math>P(m,n):=0^\infty\;3^m\;\textrm{A>}\;02\;0^n</math>. After 14 steps this configuration becomes
| | |
| <math>0^\infty\;3^{m+3}\;\textrm{<A}\;2\;0^{n-2}</math>. We note the following shift rule:
| | It is closely related to the machine [[Antihydra]].<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> |
| <math display="block">\begin{array}{|c|}\hline3^s\;\textrm{<A}\xrightarrow{s}\textrm{<A}\;3^s\\\hline\end{array}</math>
| | |
| Using this shift rule, we get <math>0^\infty\;\textrm{<A}\;3^{m+3}\;2\;0^{n-2}</math> in <math>m+3</math> steps. From here, we can observe that <math>\textrm{A>}\;0\;3^s</math> turns into <math>3\;\textrm{A>}\;0\;3^{s-1}</math> in three steps if <math>s\ge 1</math>. By repeating this process, we acquire this transition rule:
| | The sequence calculated by Hydra is a [[consistent Collatz]] sequence, (which implies, among other things, that its odd/even pattern can be calculated in quasilinear time). In the first 60 million elements, there are 29995836 even values of <code>a</code> and 30004165 odd values; thus, is known that Hydra cannot halt within the first 90 million Collatz iterations. |
| <math display="block">\begin{array}{|c|}\hline\textrm{A>}\;0\;3^s\xrightarrow{3s}3^s\;\textrm{A>}\;0\\\hline\end{array}</math>
| | |
| With this rule, it takes <math>3m+9</math> steps to reach the configuration <math>0^\infty\;3^{m+3}\;\textrm{A>}\;02\;0^{n-2}</math>, which is the same configuration as <math>P(m+3,n-2)</math>. To summarize:
| | An older simulator for the odd/even sequence used by Hydra is available [http://nethack4.org/esolangs/fasthydra.zip here], but it runs in <math>O(n^2)</math> time and thus is unusably slow compared to the consistent Collatz simulation approach. |
| <math display="block">\begin{array}{|c|}\hline P(m,n)\xrightarrow{4m+26}P(m+3,n-2)\text{ if }n\ge 2.\\\hline\end{array}</math>
| | |
| With <math>C(a,b)</math> we have <math>P(0,a)</math>. As a result, we can apply this rule <math display="inline">\big\lfloor\frac{1}{2}a\big\rfloor</math> times, which creates two possible scenarios:
| | == Name == |
| #If <math>a\equiv0\ (\operatorname{mod}2)</math>, then in <math>\sum_{i=0}^{(a/2)-1}(4\times 3i+26)=\textstyle\frac{3}{2}a^2+10a</math> steps we arrive at <math display="inline">P\Big(\frac{3}{2}a,0\Big)</math>. The matching complete configuration is <math>0^\infty\;3^{(3/2)a}\;\textrm{A>}\;02\;3^b\;2\;0^\infty</math>, which in four steps becomes <math>0^\infty\;3^{(3/2)a+1}\;1\;\textrm{A>}\;3^b\;2\;0^\infty.</math> If <math>b=0</math> then we have reached the undefined <code>A2</code> transition in <math display="inline">\frac{3}{2}a^2+10a+4</math> steps total. Otherwise, continuing for three steps gives us <math>0^\infty\;3^{(3/2)+2}\;\textrm{<B}\;0\;3^{b-1}\;2\;0^\infty</math>. Another shift rule is required here:<math display="block">\begin{array}{|c|}\hline3^s\;\textrm{<B}\xrightarrow{s}\textrm{<B}\;0^s\\\hline\end{array}</math>This means the configuration becomes <math>0^\infty\;\textrm{<B}\;0^{(3/2)a+3}\;3^{b-1}\;2\;0^\infty</math> in <math display="inline">\frac{3}{2}a+2</math> steps, and <math>0^\infty\;\textrm{<A}\;2\;0^{(3/2)a+3}\;3^{b-1}\;2\;0^\infty</math>, equal to <math display="inline">C\Big(\frac{3}{2}a+3,b-1\Big)</math>, one step later. This gives a total of <math display="inline">\frac{3}{2}a^2+\frac{23}{2}a+10</math> steps.
| | |
| #If <math>a\equiv1\ (\operatorname{mod}2)</math>, then in <math display="inline">\frac{3}{2}a^2+7a-\frac{17}{2}</math> steps we arrive at <math display="inline">P\Big(\frac{3a-3}{2},1\Big)</math>. The matching complete configuration is <math>0^\infty\;3^{(3a-3)/2}\;\textrm{A>}\;020\;3^b\;2\;0^\infty</math>, which in four steps becomes <math>0^\infty\;3^{(3a-1)/2}\;1\;\textrm{A>}\;0\;3^b\;2\;0^\infty</math>, and then <math>0^\infty\;3^{(3a-1)/2}\;1\;3^b\;\textrm{A>}\;02\;0^\infty</math> in <math>3b</math> steps. After 14 steps, we see the configuration <math>0^\infty\;3^{(3a-1)/2}\;1\;3^{b+3}\;\textrm{<A}\;2\;0^\infty</math>, which turns into <math>0^\infty\;3^{(3a-1)/2}\;1\;\textrm{<A}\;3^{b+3}\;2\;0^\infty</math> in <math>b+3</math> steps. In two steps we get <math>0^\infty\;3^{(3a+1)/2}\;\textrm{<B}\;0\;3^{b+2}\;2\;0^\infty</math>, followed by <math>0^\infty\;\textrm{<B}\;0^{(3a+3)/2}\;3^{b+2}\;2\;0^\infty</math> after another <math display="inline">\frac{3a+1}{2}</math> steps. We conclude with <math>0^\infty\;\textrm{<A}\;2\;0^{(3a+3)/2}\;3^{b+2}\;2\;0^\infty</math>, equal to <math display="inline">C\Big(\frac{3a+3}{2},b+2\Big)</math>, one step later. This gives a total of <math display="inline">4b+\frac{3}{2}a^2+\frac{17}{2}a+16</math> steps.
| | The name ''Hydra'' references the Ancient Greek legend: just as the legendary creature was growing 2 heads after losing 1 head, the ''b'' counter that is kept on the right side of the tape either increases by 2 or decreases by 1 (approximately with equal frequency if modelled as a random process; in reality it depends on the parity of ''a''). The Hydra dies (halts) when the last head is cut. |
| The information above can be summarized as
| | |
| <math display="block">C(a,b)\rightarrow\begin{cases}0^\infty\;3^{(3/2)a+1}\;1\;\textrm{A>}\;2\;0^\infty&\text{if }a\equiv0\pmod{2}\text{ and }b=0,\\C\Big(\frac{3}{2}a+3,b-1\Big)&\text{if }a\equiv0\pmod{2}\text{ and }b>0,\\C\Big(\frac{3a+3}{2},b+2\Big)&\text{if }a\equiv1\pmod2.\end{cases}</math> | | ==Sources== |
| Substituting <math>a\leftarrow 2a</math> for the first two cases and <math>a\leftarrow 2a+1</math> for the third yields the final result.
| | <references/> |
| == Trajectory ==
| |
| It takes 20 steps to reach the configuration <math>C(3,0)</math>, and from there, the [[Collatz-like]] rules are repeatedly applied. Here are the first few iterations: | |
| [[File:Hydra 0-572.gif|right|thumb|Animation of the blank tape becoming <math>C(21,0)</math> in 572 steps (''[https://wiki.bbchallenge.org/w/images/2/2f/Hydra_0-572.gif click to view]'').]]
| |
| <math display="block">\begin{array}{|c|}\hline C(3,0)\xrightarrow{55}C(6,2)\xrightarrow{133}C(12,1)\xrightarrow{364}C(21,0)\xrightarrow{856}C(33,2)\xrightarrow{1938}C(51,4)\rightarrow\cdots\\\hline\end{array}</math>
| |
| After 60 million rule steps, there are 29995836 even values of <math>a</math> and 30004165 odd values, giving a very high <math>b</math> value. However, this does not sufficiently prove that Hydra does not halt.
| |
| ===A heuristic nonhalting argument===
| |
| The trajectory of <math>b</math> values can be approximated by a random walk, where the walker can only move in step sizes +2 or -1 with equal probability, starting at position 0. The expected position of the walker after <math>k</math> steps is <math display="inline">\frac{1}{2}k</math>, and it can be shown that the probability of the walker reaching position -1 from position <math>n</math> is <math display="inline">{\Big(\frac{\sqrt{5}-1}{2}\Big)}^{n+1}</math>.
| |
| <div class="toccolours mw-collapsible mw-collapsed">'''Proof'''<div class="mw-collapsible-content">
| |
| Let <math>P(n)</math> denote the probability of the random walker reaching position 0 from position <math>n</math>. If the walker reaches position 0, it will do so either by first moving +2 with probability <math display="inline">\frac{1}{2}</math> or first moving -1 with probability <math display="inline">\frac{1}{2}</math>. Therefore, the recurrence relation is
| |
| <math display="block">\textstyle P(n)=\frac{1}{2}P(n+2)+\frac{1}{2}P(n-1)\text{ for }n\ge1.</math>
| |
| Bringing all terms with <math>P</math> to the left side of the equation and then substituting <math>n\leftarrow n+1</math> gives
| |
| <math display="block">\textstyle P(n+1)-\frac{1}{2}P(n+3)-\frac{1}{2}P(n)=0.</math>
| |
| This equation has the form <math>\sum_{i=0}^k a_iP(n+i)=0</math>, which can be solved using the zeroes of the characteristic polynomial <math>f(z)=\sum_{i=0}^k a_iz^i</math>. In this instance we get <math display="inline">f(z)=-\frac{1}{2}+z-\frac{1}{2}z^3</math>, whose zeroes are given by
| |
| <math display="block">\textstyle z_0=\frac{\sqrt{5}-1}{2},\qquad\qquad z_1=1,\qquad\qquad z_2=-\frac{1+\sqrt{5}}{2}.</math>
| |
| For each real root <math>z_i</math> with multiplicity 1, its fundamental solution is <math>c_i{\left(z_i\right)}^n</math>, and combining these fundamental solutions produces the general solution. Therefore,
| |
| <math display="block">\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</math>
| |
| The boundary condition <math>\lim_{n\to\infty} P(n)=0</math> means <math>c_2=0</math> (since <math display="inline">\left\vert-\frac{1+\sqrt{5}}{2}\right\vert > 1</math>) and <math>c_1=0</math>, and the boundary condition <math>P(0)=1</math> requires that <math>c_0=1</math>.
| |
|
| |
|
| Finally, we note that reaching position -1 from position <math>n</math>, the required condition for halting, is the same as reaching position 0 from position <math>n+1</math>, so we must increment <math>n</math>.
| | [[Category:Stub]] |
| </div></div>
| |
| For these reasons, Hydra is considered to be a [[probviously]] nonhalting machine.
| |
| ==References==
| |
| [[Category:Cryptids]] | | [[Category:Cryptids]] |
Unsolved problem:
Does Hydra run forever?
1RB3RB---3LA1RA_2LA3RA4LB0LB0LA (bbch)
Hydra is a BB(2,5) machine that simulates the Collatz-like iteration
starting from
, using configurations of the form
.
[1]
It is closely related to the machine Antihydra.[2]
The sequence calculated by Hydra is a consistent Collatz sequence, (which implies, among other things, that its odd/even pattern can be calculated in quasilinear time). In the first 60 million elements, there are 29995836 even values of a and 30004165 odd values; thus, is known that Hydra cannot halt within the first 90 million Collatz iterations.
An older simulator for the odd/even sequence used by Hydra is available here, but it runs in 
time and thus is unusably slow compared to the consistent Collatz simulation approach.
Name
The name Hydra references the Ancient Greek legend: just as the legendary creature was growing 2 heads after losing 1 head, the b counter that is kept on the right side of the tape either increases by 2 or decreases by 1 (approximately with equal frequency if modelled as a random process; in reality it depends on the parity of a). The Hydra dies (halts) when the last head is cut.
Sources
