Hydra

Unsolved problem:

Does Hydra run forever?

1RB3RB---3LA1RA_2LA3RA4LB0LB0LA (bbch)

Hydra is a BB(2,5) machine that simulates the Collatz-like iteration

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

starting from $C(3,0)$, using configurations of the form $C(a+2,b)=0^{\infty }\;<B\;0^{3a}\;3^{b}\;2\;0^{\infty }$.

It is closely related to the machine Antihydra.

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 $O(n^{2})$ 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.