Inverse Structure, Regular Languages, and Automaticity in the Collatz Dynamics

We study the Collatz dynamics via the induced map on odd integers and its inverse graph. By quotienting out powers of two, the forward dynamics become deterministic on odd states, while the inverse dynamics exhibit infinite growth. We show that each inverse cone of odd predecessors is a single infinite linear vine generated by a simple recursion. We prove that these predecessor sets correspond exactly to regular languages and that the full inverse Syracuse graph admits an automatic presentation. This reframes the Collatz problem as a termination question for a fixed infinite-state program whose inverse semantics are finite-state and structurally simple.