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.

A fast simulator for the odd/even sequence used by Hydra is available here.

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.