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}{lllll}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^{\mathrm{\infty }}<B{0}^{3a}{3}^{b}20^{\mathrm{\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.