  The Collatz process is defined on natural numbers by iterating the map $T(x)
= T_0(x) = x/2$ when $x\in\mathbb{N}$ is even and $T(x)=T_1(x) =(3x+1)/2$ when
$x$ is odd. In an effort to understand its dynamics, and since Generalised
Collatz Maps are known to simulate Turing Machines [Conway, 1972], it seems
natural to ask what kinds of algorithmic behaviours it embeds. We define a
quasi-cellular automaton that exactly simulates the Collatz process on the
square grid: on input $x\in\mathbb{N}$, written horizontally in base 2,
successive rows give the Collatz sequence of $x$ in base 2. We show that
vertical columns simultaneously iterate the map in base 3. This leads to our
main result: the Collatz process embeds an algorithm that converts any natural
number from base 3 to base 2. We also find that the evolution of our automaton
computes the parity of the number of 1s in any ternary input. It follows that
predicting about half of the bits of the iterates $T^i(x)$, for $i = O(\log
x)$, is in the complexity class NC$^1$ but outside AC$^0$. Finally, we show
that in the extension of the Collatz process to numbers with infinite binary
expansions ($2$-adic integers) [Lagarias, 1985], our automaton encodes the
cyclic Collatz conjecture as a natural reachability problem. These results show
that the Collatz process is capable of some simple, but non-trivial,
computation in bases 2 and 3, suggesting an algorithmic approach to thinking
about existence, prediction and structure of cycles in the Collatz process.
