Hydra

Hydra is the 2-state 5-symbol machine 1RB3RB---3LA1RA_2LA3RA4LB0LB0LA (bbch).

It 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)$.

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 is either decremented by or 1 incremented by 2 (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.