Hydra function: Difference between revisions

Revision as of 00:02, 4 March 2025

A bitmap depiction of 255 iterations of the Hydra function, starting with 3 at the top.

The Hydra function is a Collatz-like function whose behavior is connected to the unsolved halting problems for the Cryptids Hydra and Antihydra. It is defined as: $H (n) \equiv n + ⌊ \frac{1}{2} n ⌋ = ⌊ \frac{3}{2} n ⌋ = {\begin{cases} \frac{3 n}{2} & if n \equiv 0 (\mod 2) \\ \frac{3 n - 1}{2} & if n \equiv 1 (\mod 2) \end{cases}$ which can alternatively be written as $\begin{array}{l} H (2 n) & = & 3 n \\ H (2 n + 1) & = & 3 n + 1 \end{array}$ It has some connections to Mahler's 3/2 problem.

Relationship to Hydra and Antihydra (improved)

Recall the high-level rules for Hydra and Antihydra:

Hydra	Antihydra
Let $C (a, b) : = 0^{\infty} < A 2 0^{a} 3^{b} 2 0^{\infty}$ : $\begin{array}{lll} 0^{\infty} A > 0^{\infty} & \overset{20}{\to} & C (3, 0), \\ C (2 a, 0) & \overset{6 a^{2} + 20 a + 4}{\to} & 0^{\infty} 3^{3 a + 1} 1 A > 2 0^{\infty}, \\ C (2 a, b + 1) & \overset{6 a^{2} + 23 a + 10}{\to} & C (3 a + 3, b), \\ C (2 a + 1, b) & \overset{4 b + 6 a^{2} + 23 a + 26}{\to} & C (3 a + 3, b + 2) . \end{array}$	$A (a, b) : = 0^{\infty} 1^{a} 0 1^{b} E > 0^{\infty}$ : $\begin{array}{lll} 0^{\infty} A > 0^{\infty} & \overset{11}{\to} & A (0, 4), \\ A (a, 2 b) & \overset{2 a + 3 b^{2} + 12 b + 11}{\to} & A (a + 2, 3 b + 2), \\ A (0, 2 b + 1) & \overset{3 b^{2} + 9 b - 1}{\to} & 0^{\infty} < F 110 1^{3 b} 0^{\infty}, \\ A (a + 1, 2 b + 1) & \overset{3 b^{2} + 12 b + 5}{\to} & A (a, 3 b + 3) . \end{array}$

Already, both machines can be observed to have very similar functions. Both have one parameter that increases exponentially with growth factor $\frac{3}{2}$ , and another that takes a pseudo-random walk that depends on the parity of the other variable. This relationship can be strengthened through a change of variables. This is easier to illustrate if these rules were written in the form of integer sequences:

Hydra	Antihydra
$a_{0} = 3, a_{n + 1} = {\begin{cases} \frac{3 a_{n} + 6}{2} & if a_{n} \equiv 0 (\mod 2) \\ \frac{3 a_{n} + 3}{2} & if a_{n} \equiv 1 (\mod 2) \end{cases}$	$a_{0} = 4, a_{n + 1} = {\begin{cases} \frac{3 a_{n} + 4}{2} & if a_{n} \equiv 0 (\mod 2) \\ \frac{3 a_{n} + 3}{2} & if a_{n} \equiv 1 (\mod 2) \end{cases}$

Now, we will introduce a new integer sequence based on the old one and discover the recursive rules for that sequence. For Hydra, this new sequence is $b_{n} = \frac{1}{3} a_{n} + 2$ . For Antihydra, this new sequence is $b_{n} = a_{n} + 4$ . The new rules are found by using $b_{n + 1}$ instead and substituting $a_{n + 1}$ for its recursive formula. By doing so, we get:

Hydra	Antihydra
$b_{0} = 3, b_{n + 1} = {\begin{cases} \frac{a_{n} + 6}{2} & if a_{n} \equiv 0 (\mod 2) \\ \frac{a_{n} + 5}{2} & if a_{n} \equiv 1 (\mod 2) \end{cases}$	$b_{0} = 8, b_{n + 1} = {\begin{cases} \frac{3 a_{n} + 12}{2} & if a_{n} \equiv 0 (\mod 2) \\ \frac{3 a_{n} + 11}{2} & if a_{n} \equiv 1 (\mod 2) \end{cases}$

After that, we must substitute $a_{n}$ for its solution in terms of $b_{n}$ . What results is the following:

Hydra	Antihydra
$b_{0} = 3, b_{n + 1} = {\begin{cases} \frac{3 (b_{n} - 2) + 6}{2} & if 3 (b_{n} - 2) \equiv 0 (\mod 2) \\ \frac{3 (b_{n} - 2) + 5}{2} & if 3 (b_{n} - 2) \equiv 1 (\mod 2) \end{cases}$	$b_{0} = 8, b_{n + 1} = {\begin{cases} \frac{3 (b_{n} - 4) + 12}{2} & if b_{n} - 4 \equiv 0 (\mod 2) \\ \frac{3 (b_{n} - 4) + 11}{2} & if b_{n} - 4 \equiv 1 (\mod 2) \end{cases}$

We finish by noting that the if statements simplify to simply checking if $b_{n}$ is even or odd. After simplifying, we get

Hydra	Antihydra
$b_{0} = 3, b_{n + 1} = {\begin{cases} \frac{3 b_{n}}{2} & if b_{n} \equiv 0 (\mod 2) \\ \frac{3 b_{n} - 1}{2} & if b_{n} \equiv 1 (\mod 2) \end{cases}$	$b_{0} = 8, b_{n + 1} = {\begin{cases} \frac{3 b_{n}}{2} & if b_{n} \equiv 0 (\mod 2) \\ \frac{3 b_{n} - 1}{2} & if b_{n} \equiv 1 (\mod 2) \end{cases}$

Properties

Here, $s$ and $t$ are positive integers with $t$ odd. Let $0 \leq k \leq s$ be an integer and $H^{k}$ is the $k$ th iterate of $H$ . $\begin{array}{l} H^{k} (2^{s} t) & = & 3^{k} 2^{s - k} t \\ H^{k} (2^{s} t + 1) & = & 3^{k} 2^{s - k} t + 1 \end{array}$

@@ Line 1: / Line 1: @@
-[[File:Hydra-function-bitmap-255iterations.svg|thumb|A bitmap depiction of 255 iterations of the Hydra function, starting with 3 at the top.]]
+[[File:Hydra-function-bitmap-255iterations.svg|thumb|100px|A bitmap depiction of 255 iterations of the Hydra function, starting with 3 at the top.]]
 The '''Hydra function''' is a [[Collatz-like]] function whose behavior is connected to the unsolved halting problems for the [[Cryptids]] [[Hydra]] and [[Antihydra]]. It is defined as:
 <math display="block">\textstyle H(n)\equiv n+\left\lfloor\frac{1}{2}n\right\rfloor=\Big\lfloor\frac{3}{2}n\Big\rfloor=\begin{cases}
@@ Line 11: / Line 11: @@
 \end{array}</math>
 It has some connections to [[wikipedia:Mahler's_3/2_problem|Mahler's 3/2 problem]].
+== Relationship to Hydra and Antihydra (improved)==
+Recall the high-level rules for Hydra and Antihydra:
+{|class="wikitable"
+! Hydra !! Antihydra
+|-align="center"
+|Let <math>C(a,b):=0^\infty\;\textrm{<A}\;2\;0^a\;3^b\;2\;0^\infty</math>:<math display="block">\begin{array}{|lll|}\hline
+^\infty\;\textrm{A>}\;0^\infty&\xrightarrow{20}&C(3,0),\\
+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>
+|<math>A(a,b):=0^\infty\;1^a\;0\;1^b\;\textrm{E>}\;0^\infty</math>:<math display="block">\begin{array}{|lll|}\hline
+^\infty\;\textrm{A>}\;0^\infty&\xrightarrow{11}&A(0,4),\\
+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}</math>
+|}
+Already, both machines can be observed to have very similar functions. Both have one parameter that increases exponentially with growth factor <math display="inline">\frac{3}{2}</math>, and another that takes a pseudo-random walk that depends on the parity of the other variable. This relationship can be strengthened through a change of variables. This is easier to illustrate if these rules were written in the form of integer sequences:
+{|class="wikitable"
+! Hydra !! Antihydra
+|-align="center"
+|<math display="block">a_0=3,a_{n+1}=\begin{cases}\frac{3a_n+6}{2}&\text{if }a_n\equiv0\pmod{2}\\\frac{3a_n+3}{2}&\text{if }a_n\equiv1\pmod{2}\end{cases}</math>
+|<math display="block">a_0=4,a_{n+1}=\begin{cases}\frac{3a_n+4}{2}&\text{if }a_n\equiv0\pmod{2}\\\frac{3a_n+3}{2}&\text{if }a_n\equiv1\pmod{2}\end{cases}</math>
+|}
+Now, we will introduce a new integer sequence based on the old one and discover the recursive rules for that sequence. For Hydra, this new sequence is <math display="inline">b_n=\frac{1}{3}a_n+2</math>. For Antihydra, this new sequence is <math>b_n=a_n+4</math>. The new rules are found by using <math>b_{n+1}</math> instead and substituting <math>a_{n+1}</math> for its recursive formula. By doing so, we get:
+{|class="wikitable"
+! Hydra !! Antihydra
+|-align="center"
+|<math display="block">b_0=3,b_{n+1}=\begin{cases}\frac{a_n+6}{2}&\text{if }a_n\equiv0\pmod{2}\\\frac{a_n+5}{2}&\text{if }a_n\equiv1\pmod{2}\end{cases}</math>
+|<math display="block">b_0=8,b_{n+1}=\begin{cases}\frac{3a_n+12}{2}&\text{if }a_n\equiv0\pmod{2}\\\frac{3a_n+11}{2}&\text{if }a_n\equiv1\pmod{2}\end{cases}</math>
+|}
+After that, we must substitute <math>a_n</math> for its solution in terms of <math>b_n</math>. What results is the following:
+{|class="wikitable"
+! Hydra !! Antihydra
+|-align="center"
+|<math display="block">b_0=3,b_{n+1}=\begin{cases}\frac{3(b_n-2)+6}{2}&\text{if }3(b_n-2)\equiv0\pmod{2}\\\frac{3(b_n-2)+5}{2}&\text{if }3(b_n-2)\equiv1\pmod{2}\end{cases}</math>
+|<math display="block">b_0=8,b_{n+1}=\begin{cases}\frac{3(b_n-4)+12}{2}&\text{if }b_n-4\equiv0\pmod{2}\\\frac{3(b_n-4)+11}{2}&\text{if }b_n-4\equiv1\pmod{2}\end{cases}</math>
+|}
+We finish by noting that the if statements simplify to simply checking if <math>b_n</math> is even or odd. After simplifying, we get
+{|class="wikitable"
+! Hydra !! Antihydra
+|-align="center"
+|<math display="block">b_0=3,b_{n+1}=\begin{cases}\frac{3b_n}{2}&\text{if }b_n\equiv0\pmod{2}\\\frac{3b_n-1}{2}&\text{if }b_n\equiv1\pmod{2}\end{cases}</math>
+|<math display="block">b_0=8,b_{n+1}=\begin{cases}\frac{3b_n}{2}&\text{if }b_n\equiv0\pmod{2}\\\frac{3b_n-1}{2}&\text{if }b_n\equiv1\pmod{2}\end{cases}</math>
+|}
 ==Properties==
 Here, <math>s</math> and <math>t</math> are positive integers with <math>t</math> odd. Let <math>0\le k\le s</math> be an integer and <math>H^k</math> is the <math>k</math>th iterate of <math>H</math>.
@@ Line 17: / Line 63: @@
    H^k(2^s t+1)   & = & 3^k2^{s-k}t+1 \\
 \end{array}</math>
-==Relationship to Hydra and Antihydra==
-Both machines effectively track the progress of two variables; one of them changes depending on its value modulo 2 but roughly multiplies itself by <math>\frac{3}{2}</math>, and the other increases by 2 or decreases by 1 depending on the parity of the first variable.
-In particular, Hydra halts if and only if the sequence
-<math display="block">a(n+1)=\begin{cases}\frac{3\times a(n)+6}{2}&\text{if }a(n)\equiv0\pmod{2}\\\frac{3\times a(n)+3}{2}&\text{if }a(n)\equiv1\pmod{2}\end{cases}</math>
-ever has more even terms than twice the number of odd terms, starting with <math>a(0)=3</math>. Similarly, Antihydra halts if and only if the sequence
-<math display="block">a(n+1)=\begin{cases}\frac{3\times a(n)+4}{2}&\text{if }a(n)\equiv0\pmod{2}\\\frac{3\times a(n)+3}{2}&\text{if }a(n)\equiv1\pmod{2}\end{cases}</math>
-ever has more odd terms than twice the number of even terms, starting with <math>a(0)=4</math>.
-For Hydra, we can introduce the sequence <math>b(n)=\frac{1}{3}a(n)+2</math> whose terms have the same sequence of parities as <math>a(n)</math>. Then we have:
-<math display="block">\begin{array}{l}
-  b(n+1)& = & \frac{1}{3}a(n+1)+2 \\
-  b(n+1)& = &2+\frac{1}{3}\begin{cases}\frac{3\times a(n)+6}{2}&\text{if }a(n)\equiv0\pmod{2}\\\frac{3\times a(n)+3}{2}&\text{if }a(n)\equiv1\pmod{2}\end{cases}\\
-b(n+1)&=&\begin{cases}\frac{a(n)+6}{2}&\text{if }a(n)\equiv0\pmod{2}\\\frac{a(n)+5}{2}&\text{if }a(n)\equiv1\pmod{2}\end{cases}\\
-b(n+1)&=&\begin{cases}\frac{3(b(n)-2)+6}{2}&\text{if }3(b(n)-2)\equiv0\pmod{2}\\\frac{3(b(n)-2)+5}{2}&\text{if }3(b(n)-2)\equiv1\pmod{2}\end{cases}\\
-b(n+1)&=&\begin{cases}\frac{3b(n)}{2}&\text{if }b(n)\equiv0\pmod{2}\\\frac{3b(n)-1}{2}&\text{if }b(n)\equiv1\pmod{2}\end{cases}\\
-\end{array}</math>
-For Antihydra, we can repeat this but with the sequence <math>b(n)=a(n)+4</math>.

Hydra function: Difference between revisions

Revision as of 00:02, 4 March 2025

Relationship to Hydra and Antihydra (improved)

Properties

Navigation menu

Search