Hydra function

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+\lfloor \frac{1}{2}n\rfloor =\lfloor \frac{3}{2}n\rfloor =\{\begin{array}{ll}\frac{3n}{2}& \text{if }n\equiv 0(\mathrm{mod}2)\\ \frac{3n-1}{2}& \text{if }n\equiv 1(\mathrm{mod}2)\\ \end{array}$$ which can alternatively be written as $$\begin{array}{lll}H(2n)& =& 3n\\ H(2n+1)& =& 3n+1\\ \end{array}$$ It has some connections to Mahler's 3/2 problem.

Relationship to Hydra and Antihydra

Recall the high-level rules for Hydra and Antihydra:

Hydra

Antihydra

Let $C(a,b):=0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}20^a{3}^{b}20^{\mathrm{\infty }}$:$$\begin{array}{lll}{0}^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}& \stackrel{20}{\to }& C(3,0),\\ C(2a,0)& \stackrel{6a^2+20a+4}{\to }& 0^{\mathrm{\infty }}{3}^{3a+1}1\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}20^{\mathrm{\infty }},\\ C(2a,b+1)& \stackrel{6a^2+23a+10}{\to }& C(3a+3,b),\\ C(2a+1,b)& \stackrel{4b+6a^2+23a+26}{\to }& C(3a+3,b+2).\end{array}$$

Let $A(a,b):=0^{\mathrm{\infty }}{1}^{a}01^b\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$:$$\begin{array}{lll}{0}^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}& \stackrel{11}{\to }& A(0,4),\\ A(a,2b)& \stackrel{2a+3b^2+12b+11}{\to }& A(a+2,3b+2),\\ A(0,2b+1)& \stackrel{3b^2+9b-1}{\to }& 0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>F</mrow>}1101^{3b}{0}^{\mathrm{\infty }},\\ A(a+1,2b+1)& \stackrel{3b^2+12b+5}{\to }& A(a,3b+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{array}{ll}\frac{3a_n+6}{2}& \text{if }{a}_n\equiv 0(\mathrm{mod}2)\\ \frac{3a_n+3}{2}& \text{if }{a}_n\equiv 1(\mathrm{mod}2)\end{array}$$	$$a_0=4,a_{n+1}=\{\begin{array}{ll}\frac{3a_n+4}{2}& \text{if }{a}_n\equiv 0(\mathrm{mod}2)\\ \frac{3a_n+3}{2}& \text{if }{a}_n\equiv 1(\mathrm{mod}2)\end{array}$$

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{array}{ll}\frac{a_n+6}{2}& \text{if }{a}_n\equiv 0(\mathrm{mod}2)\\ \frac{a_n+5}{2}& \text{if }{a}_n\equiv 1(\mathrm{mod}2)\end{array}$$	$$b_0=8,b_{n+1}=\{\begin{array}{ll}\frac{3a_n+12}{2}& \text{if }{a}_n\equiv 0(\mathrm{mod}2)\\ \frac{3a_n+11}{2}& \text{if }{a}_n\equiv 1(\mathrm{mod}2)\end{array}$$

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{array}{ll}\frac{3(b_n-2)+6}{2}& \text{if }3(b_n-2)\equiv 0(\mathrm{mod}2)\\ \frac{3(b_n-2)+5}{2}& \text{if }3(b_n-2)\equiv 1(\mathrm{mod}2)\end{array}$$	$$b_0=8,b_{n+1}=\{\begin{array}{ll}\frac{3(b_n-4)+12}{2}& \text{if }{b}_n-4\equiv 0(\mathrm{mod}2)\\ \frac{3(b_n-4)+11}{2}& \text{if }{b}_n-4\equiv 1(\mathrm{mod}2)\end{array}$$

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{array}{ll}\frac{3b_n}{2}& \text{if }{b}_n\equiv 0(\mathrm{mod}2)\\ \frac{3b_n-1}{2}& \text{if }{b}_n\equiv 1(\mathrm{mod}2)\end{array}$$	$$b_0=8,b_{n+1}=\{\begin{array}{ll}\frac{3b_n}{2}& \text{if }{b}_n\equiv 0(\mathrm{mod}2)\\ \frac{3b_n-1}{2}& \text{if }{b}_n\equiv 1(\mathrm{mod}2)\end{array}$$

Now that we have demonstrated the relatedness between the behaviour of both Turing machines, we can return to using the high-level rules. Once we do this, the result is:

Hydra

Antihydra

Let $C(a,b):=0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}20^{3(a-2)}{3}^{b}20^{\mathrm{\infty }}$:$$\begin{array}{lll}{0}^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}& \stackrel{20}{\to }& C(3,0),\\ C(2a,0)& \stackrel{54a^2-48a-2}{\to }& 0^{\mathrm{\infty }}{3}^{9a-8}1\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}20^{\mathrm{\infty }},\\ C(2a,b+1)& \stackrel{54a^2-39a-5}{\to }& C(3a,b),\\ C(2a+1,b)& \stackrel{4b+54a^2-3a+4}{\to }& C(3a+1,b+2).\end{array}$$

$A(a,b):=0^{\mathrm{\infty }}{1}^{a}01^{b-4}\text{<mrow data-mjx-texclass="ORD">E<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$:$$\begin{array}{lll}{0}^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}& \stackrel{11}{\to }& A(0,8),\\ A(a,2b)& \stackrel{2a+3b^2-1}{\to }& A(a+2,3b),\\ A(0,2b+1)& \stackrel{3b^2-3b-7}{\to }& 0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>F</mrow>}1101^{3b-6}{0}^{\mathrm{\infty }},\\ A(a+1,2b+1)& \stackrel{3b^2-7}{\to }& A(a,3b+1).\end{array}$$

Properties

Here, $s$ and $t$ are positive integers with $t$ odd. Let $0\le k\le s$ be an integer and $H^k$ is the $k$th iterate of $H$. $$\begin{array}{lll}{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}$$