Logical Undefinability of the Generalized Collatz Transition Relation in Büchi Arithmetic

Abstract

Let $q$ be an odd prime and let $d$ be an odd integer. We show that the arbitrary-step transition relation of the generalized Collatz map $T_{q,d}$ is not first-order definable in Base-2 Büchi Arithmetic ($B{A}_2$). We do this by demonstrating that if the transition relation were definable, the exponential set $P_q=\{q^y:y\in \mathbb{N}\}$ would also be definable in $B{A}_2$. Since $P_q$ is strictly non-semilinear, this yields a direct contradiction with the Cobham--Semënov theorem. Consequently, we demonstrate that no finite automaton reading base-2 representations can recognize this transition relation.

6 pages