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:

$$\textstyle H(n)\equiv n+\left\lfloor {\frac {1}{2}}n\right\rfloor ={\Big \lfloor }{\frac {3}{2}}n{\Big \rfloor }={\begin{cases}{\frac {3n}{2}}&{\text{if }}n\equiv 0{\pmod {2}}\\{\frac {3n-1}{2}}&{\text{if }}n\equiv 1{\pmod {2}}\\\end{cases}}$$

which can alternatively be written as

$${\begin{array}{l}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^{\infty }\;{\textrm {<A}}\;2\;0^{a}\;3^{b}\;2\;0^{\infty }$: $${\begin{array}{|lll|}\hline 0^{\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}}$$

Let $A(a,b):=0^{\infty }\;1^{a}\;0\;1^{b}\;{\textrm {E>}}\;0^{\infty }$: $${\begin{array}{|lll|}\hline 0^{\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}}$$

Already, both machines can be observed to have very similar functions. Both have one parameter that increases exponentially with growth factor ${\textstyle {\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 {3a_{n}+6}{2}}&{\text{if }}a_{n}\equiv 0{\pmod {2}}\\{\frac {3a_{n}+3}{2}}&{\text{if }}a_{n}\equiv 1{\pmod {2}}\end{cases}}$$	$$a_{0}=4,a_{n+1}={\begin{cases}{\frac {3a_{n}+4}{2}}&{\text{if }}a_{n}\equiv 0{\pmod {2}}\\{\frac {3a_{n}+3}{2}}&{\text{if }}a_{n}\equiv 1{\pmod {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 ${\textstyle 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}}&{\text{if }}a_{n}\equiv 0{\pmod {2}}\\{\frac {a_{n}+5}{2}}&{\text{if }}a_{n}\equiv 1{\pmod {2}}\end{cases}}$$	$$b_{0}=8,b_{n+1}={\begin{cases}{\frac {3a_{n}+12}{2}}&{\text{if }}a_{n}\equiv 0{\pmod {2}}\\{\frac {3a_{n}+11}{2}}&{\text{if }}a_{n}\equiv 1{\pmod {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}}&{\text{if }}3(b_{n}-2)\equiv 0{\pmod {2}}\\{\frac {3(b_{n}-2)+5}{2}}&{\text{if }}3(b_{n}-2)\equiv 1{\pmod {2}}\end{cases}}$$	$$b_{0}=8,b_{n+1}={\begin{cases}{\frac {3(b_{n}-4)+12}{2}}&{\text{if }}b_{n}-4\equiv 0{\pmod {2}}\\{\frac {3(b_{n}-4)+11}{2}}&{\text{if }}b_{n}-4\equiv 1{\pmod {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 {3b_{n}}{2}}&{\text{if }}b_{n}\equiv 0{\pmod {2}}\\{\frac {3b_{n}-1}{2}}&{\text{if }}b_{n}\equiv 1{\pmod {2}}\end{cases}}$$	$$b_{0}=8,b_{n+1}={\begin{cases}{\frac {3b_{n}}{2}}&{\text{if }}b_{n}\equiv 0{\pmod {2}}\\{\frac {3b_{n}-1}{2}}&{\text{if }}b_{n}\equiv 1{\pmod {2}}\end{cases}}$$

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^{\infty }\;{\textrm {<A}}\;2\;0^{3(a-2)}\;3^{b}\;2\;0^{\infty }$: $${\begin{array}{|lll|}\hline 0^{\infty }\;{\textrm {A>}}\;0^{\infty }&\xrightarrow {20} &C(3,0),\\C(2a,0)&\xrightarrow {54a^{2}-48a-2} &0^{\infty }\;3^{9a-8}\;1\;{\textrm {A>}}\;2\;0^{\infty },\\C(2a,b+1)&\xrightarrow {54a^{2}-39a-5} &C(3a,b),\\C(2a+1,b)&\xrightarrow {4b+54a^{2}-3a+4} &C(3a+1,b+2).\\\hline \end{array}}$$

$A(a,b):=0^{\infty }\;1^{a}\;0\;1^{b-4}\;{\textrm {E>}}\;0^{\infty }$: $${\begin{array}{|lll|}\hline 0^{\infty }\;{\textrm {A>}}\;0^{\infty }&\xrightarrow {11} &A(0,8),\\A(a,2b)&\xrightarrow {2a+3b^{2}-1} &A(a+2,3b),\\A(0,2b+1)&\xrightarrow {3b^{2}-3b-7} &0^{\infty }\;{\textrm {<F}}\;110\;1^{3b-6}\;0^{\infty },\\A(a+1,2b+1)&\xrightarrow {3b^{2}-7} &A(a,3b+1).\\\hline \end{array}}$$

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}}$$