A Symbolic Recursive Function and Its Possible Semi-Conjugacy with the Collatz Map

Abstract

We study a recursive function $f$ acting on finite words over the alphabet $\Sig=\{1,2\}$, defined by \[ f(1)=2,\quad f(2)=1,\qquad f(u1)=\compl{f(u)}\concat 2,\qquad f(u2)=f(f(u))\concat 1. \] We establish several structural properties (length behavior, stability of a block language, and the action on terminal blocks $1^k2$), and propose a symbolic encoding of the accelerated Collatz map on odd integers via blocks $\E(n)=1^{\Nu(3n+1)}2$. We formulate and partially justify a \emph{semi-conjugacy} principle of the form \[ N\bigl(f(\E(n))\bigr)=\E(\Hmap(n)), \] where $N$ is a fixed normalizing operator (removal of a short prefix and possibly letterwise complement). We provide proofs for the combinatorial statements and rigorous bounds for the normalization, while clearly stating which parts remain conjectural. Connections with morphic/automatic sequences and symbolic dynamics are discussed.

Keywords