2506.21728v2

# A Finite-State Symbolic Automaton Model for the Collatz Map and Its Convergence Properties **Authors**: - Leonard Ben Aurel Brauer (Independent Researcher) - ORCID: 0009-0003-9173- Abstract We present a finite-state, deterministic automaton that emulates the Collatz function through digitwise transitions on base-10 representations. Each digit is represented as a symbolic triplet $(r,p,c)$ encoding its value, the parity of the next digit, and an incoming carry propagated from the lower digit. This yields exactly 60 possible local states. The automaton applies local, parity-aware rules that collectively reconstruct the global arithmetic of the Collatz map. We show that all symbolic trajectories converge in finitely many steps to a unique terminal cycle $(4,0,0)→(2,0,0)→(1,0,0)$ , with all higher digit positions degenerating to the absorbing state $(0,0,0)$ . This collapse reveals a canonical symbolic normal form of Collatz dynamics. In parallel, a binary view explains the dynamics as alternating bit-length growth and contraction, aligning with known heuristics for Collatz convergence. This structural perspective is further reinforced by a symbolic drift function and a ranking potential that together explain and formalize the convergence process. Keywords Collatz Conjecture · Finite-State Automaton · Symbolic Arithmetic · Digitwise Dynamics · Primitive Recursion 1 Introduction Few problems in elementary mathematics are as deceptively simple and notoriously resistant as the so-called 3 $x+1$ problem. Defined by an innocuous piecewise function over the natural numbers, it asks whether repeated application of the map $$ T(n)=\begin{cases}\frac{n}{2},&\text{if }n\equiv 0\pmod{2}\\ 3n+1,&\text{if }n\equiv 1\pmod{2}\end{cases} $$ will eventually reach the value $1$ for all $n∈\mathbb{N}^{+}$ . Despite its apparent simplicity and extensive numerical verification, the conjecture—first posed by Lothar Collatz in 1937—remains unproven [1]. The difficulty lies in the absence of a known invariant or monotonicity property: trajectories exhibit nontrivial recursive fluctuations, and the function’s alternating arithmetic structure complicates analytic treatment. In this work, we present a finite-state, symbolic reformulation of the Collatz dynamics. Each base-10 digit of $n$ is represented as a triplet $(r,p,c)$ , where $r$ is the digit’s value, $p$ the parity of the next higher-order digit, and $c$ a carry propagated from lower positions. This yields a deterministic automaton with exactly $10· 2· 3=60$ distinct states. Transitions act locally on digit positions, yet collectively reproduce the global behavior of $T(n)$ via structured, digitwise updates. Each number is thus represented as a vertical stack of symbolic digit states, one per decimal place, where each column evolves independently over time. The symbolic dynamics proceed row-by-row through successive configurations, allowing the Collatz behavior to emerge from purely local interactions. We prove that all symbolic digit states eventually collapse to the null state $(0,0,0)$ , except for the least significant position. Once all higher digit positions are absorbed, the remaining state at position $s_{0}$ enters the unique three-node cycle $(4,0,0)→(2,0,0)→(1,0,0)$ , which corresponds to the classical terminal loop $4→ 2→ 1$ . No other symbolic cycles or divergent paths exist within this structure. Beyond its theoretical implications, the automaton provides a symbolic and transparent model of integer dynamics. Its local, deterministic transitions offer a natural fit for logic circuits, low-power symbolic processors, or explainable symbolic AI frameworks. The construction opens new perspectives on digit-level number theory and computationally verifiable transformations. Origin of the Approach. This work did not begin with the goal of addressing the Collatz conjecture directly, but grew out of a broader interest in how structured behavior can arise from simple symbolic rules. When the author first encountered the Collatz function—previously unfamiliar—it was immediately clear that its complex dynamics likely stem from its minimal definition, rather than from randomness. Motivated by this, a small tool was developed to visualize and explore Collatz sequences. This quickly revealed patterns at the digit level, pointing toward an underlying local regularity. One key insight was the central role of the least significant digit, $r_{0}$ : its value, together with parity and carry information, sufficed to determine the local update behavior. This prompted the design of a symbolic representation, which evolved into the deterministic automaton formalized in this study. 1.1 Related Work Numerous past and ongoing projects in number theory, dynamical systems, and symbolic computation have investigated the behavior of arithmetic iterations resembling the Collatz map, particularly with the aim of proving or disproving convergence under various formulations. An updated overview of historical and recent developments is provided by Lagarias [2], complementing his earlier annotated bibliographies [1, 3]. Residue class analysis and tree-based trajectory studies emphasize the combinatorial complexity of such functions. Tao [4] introduced a probabilistic and ergodic perspective on integer dynamics, studying the behavior of iterative maps under statistical models. This probabilistic viewpoint extends earlier work by Lagarias and Weiss [5], who developed stochastic models using biased random walks to examine the statistical behavior of Collatz trajectories, including growth rates and stopping times. The present work deviates from these global strategies by proposing a digitwise symbolic emulation using a deterministic finite-state automaton. Each digit of the input number is processed locally, enabling a structural decomposition of the transformation into symbolic transitions with bounded carry propagation. The automaton construction, along with a symbolic descent function that guarantees convergence, was developed by the author. This fine-grained representation departs from traditional whole-number views and establishes termination via symbolic state space dynamics. Foundational tools from discrete mathematics and automata theory [6, 7] underlie the definition of state transitions, carry mechanisms, and formal verification techniques used in this framework. 2 A Finite-State Symbolic Automaton for the Collatz Function We present a symbolic representation of the Collatz function acting on the base-10 digit expansion of natural numbers. This formulation encodes each digit with auxiliary state information, enabling the construction of a deterministic finite-state automaton with 60 states. Each symbolic state encodes the local configuration of a single decimal digit during a Collatz transformation step. Formally, a state is a triplet $(r_{i},p_{i},c_{i})$ where $r_{i}$ is the $i$ -th digit of the input number (in base 10), $p_{i}=r_{i+1}\bmod 2$ is the parity of the next digit and $c_{i}$ is a carry value originating from the previous digit’s computation. These states are processed sequentially from least to most significant digit, enabling the digitwise reconstruction of operations such as $3n+1$ and $n/2$ using local arithmetic and carry propagation only. The total configuration of a number is thus captured by a sequence of symbolic states indexed by digit position. 2.1 Positional Representation and Symbolic State Let $n∈\mathbb{N}$ be written as a base-10 expansion [6]: $$ n=\sum_{i=0}^{L}r_{i}\cdot 10^{i},\quad r_{i}\in\{0,1,\dots,9\} $$ where $r_{0}$ is the least significant digit and $L∈\mathbb{N}$ is the index of the most significant digit. Each digit $r_{i}$ is associated with: - its value $r_{i}∈\{0,1,...,9\}$ , - the parity of the next digit: $p_{i}:=r_{i+1}\bmod 2$ for $i<L$ ; the parity value is undefined (and unused) for $i=L$ , - a carry $c_{i}∈\{0,1,2\}$ propagated from the previous digit position, which arises as follows: - In the even case $T(n)=\lfloor n/2\rfloor$ , carries arise from parity-dependent digit borrowing. - In the odd case $T(n)=3n+1$ , carries result from digitwise multiplication with overflow. - For the least significant digit $r_{0}$ , the initial carry is fixed: $c_{0}:=0$ . We define the symbolic digit state as the triplet $s_{i}:=(r_{i},p_{i},c_{i})∈ S$ , where the finite state space is given by: $$ S:=\{0,\dots,9\}\times\{0,1\}\times\{0,1,2\},\quad|S|=60 $$ From this, a symbolic representation was developed that evolves into a finite-state automaton [7], in which each state encodes digit value, parity context, and local carry behavior. 2.2 Symbolic Transition Rules We define $\delta_{i}:S→\{0,...,9\}$ as the local digitwise output function. It maps each symbolic input state $(r_{i},p_{i},c_{i})$ to the corresponding output digit $r_{i}^{\prime}$ . The choice of update rule depends on the global parity $\pi(n):=n\bmod 2$ of the input number: $$ r_{i}^{\prime}:=\begin{cases}\delta_{\text{even}}(r_{i},p_{i},c_{i}),&\text{if }n\text{ is even},\\ \delta_{\text{odd}}(r_{i},c_{i}),&\text{if }n\text{ is odd}.\end{cases} $$ Note that $\delta_{i}$ only computes the updated digit value $r_{i}^{\prime}$ . The corresponding parity and carry values for subsequent digits are determined separately via recursive rules. 2.3 Even Case: $T(n)=\lfloor n/2\rfloor$ For even $n$ , the Collatz map halves the number. We simulate this operation digit-by-digit using a parity-aware rule. Lookup Table Representation The digitwise transformation uses a finite table that maps even digits $r_{i}∈\{0,2,4,6,8\}$ and parities $p_{i}∈\{0,1\}$ to a new symbolic digit $r_{i}^{\prime}$ : $$ r_{i}^{\prime}=\texttt{LOOKUP}\left[\,(r_{i}-c_{i})\bmod 10\,\right][\,p_{i}\,] $$ Table 1: Lookup table for even-case digit updates: columns correspond to current digit $r_{i}$ , and rows to the next-digit parity $p_{i}$ . | 0 1 | 0 5 | 1 6 | 2 7 | 3 8 | 4 9 | | --- | --- | --- | --- | --- | --- | The lookup table defines the transformation for even digits. It maps the adjusted digit $(r_{i}-c_{i})\bmod 10$ and the next-digit parity $p_{i}$ to the output digit $r_{i}^{\prime}$ . Each entry specifies the result of halving an even digit $r_{i}$ under the influence of the parity $p_{i}$ of the next digit. For example, if $n=30$ , then $r_{0}=0$ , $p_{0}=1$ , and $c_{0}=0$ , leading to $r_{0}^{\prime}=\texttt{LOOKUP}[0][1]=5$ . Closed-Form Rule with Carry The same mapping can be equivalently expressed as a closed-form update, taking into account the carry $c_{i}$ propagated from the right: $$ \delta_{\text{even}}(r_{i},p_{i},c_{i}):=\left\lfloor\frac{r_{i}-c_{i}}{2}\right\rfloor+5p_{i} $$ This rule matches the lookup behavior and ensures correct adjustment for carry-induced subtractions. Parity and Carry Propagation: $$ p_{i}:=r_{i+1}\bmod 2\qquad c_{i+1}:=\begin{cases}1&\text{if }p_{i}=1\\ 0&\text{otherwise}\end{cases} $$ This ensures that each local state $(r_{i},p_{i},c_{i})$ includes the information required to account for parity-induced division shifts, analogous to digit borrowing in manual division. 2.4 Odd Case: $T(n)=3n+1$ If $n$ is odd, the Collatz map applies $3n+1$ . We emulate this with digitwise multiplication and carry propagation. Digitwise Transition Rule For each digit index $i≥ 0$ , define: $$ \delta_{\text{odd}}(r_{i},c_{i}):=\begin{cases}(3r_{i}+1)\bmod 10&\text{if }i=0\\ (3r_{i}+c_{i})\bmod 10&\text{if }i>0\end{cases} $$ $$ c_{i+1}:=\begin{cases}\left\lfloor\frac{3r_{i}+1}{10}\right\rfloor&\text{if }i=0\\ \left\lfloor\frac{3r_{i}+c_{i}}{10}\right\rfloor&\text{if }i>0\end{cases} $$ Alternative Representation Let $n=\sum_{i=0}^{L}r_{i}· 10^{i}$ be the decimal expansion. Then: $$ T(n)=3n+1=\left(\sum_{i=0}^{L}3r_{i}\cdot 10^{i}\right)+1 $$ This expression is evaluated digitwise with carry propagation as per the recursive rules above. The symbolic update faithfully emulates this arithmetic. 2.5 Unified Digitwise Reconstruction of $T(n)$ Let $n∈\mathbb{N}^{+}$ have decimal expansion $n=\sum_{i=0}^{L}r_{i}· 10^{i}$ , and define: $$ r_{i}^{\prime}:=\begin{cases}\delta_{\text{even}}(r_{i},p_{i},c_{i})&\text{if }n\equiv 0\pmod{2}\\ \delta_{\text{odd}}(r_{i},c_{i})&\text{if }n\equiv 1\pmod{2}\end{cases} $$ Then the Collatz map is reconstructed symbolically via: $$ T(n)=\sum_{i=0}^{L^{\prime}}r_{i}^{\prime}\cdot 10^{i}\quad\text{for some }L^{\prime}\in\{L-1,L,L+1\} $$ This unified notation allows symbolic digitwise emulation of both cases of the Collatz map. 2.6 Illustrative Example: $n=27$ We illustrate the symbolic digitwise emulation for the odd input $n=27$ , where $T(27)=3· 27+1=82$ . The decimal expansion of $n$ is: $$ n=7\cdot 10^{0}+2\cdot 10^{1}\quad\Rightarrow\quad r_{0}=7,\ r_{1}=2 $$ We now apply the symbolic update rules for the odd case: | | $\displaystyle r_{0}^{\prime}$ | $\displaystyle=\delta_{\text{odd}}(7,0)=(3· 7+1)\bmod 10=2$ | | | --- | --- | --- | --- | Table 2: Symbolic digitwise transition for $n=27$ under $T(n)=3n+1$ | 0 1 | 7 2 | 0 – | 0 2 | 2 8 | 0 0 | 2 0 | | --- | --- | --- | --- | --- | --- | --- | We obtain the updated digit sequence $(r_{0}^{\prime},r_{1}^{\prime})=(2,8)$ , which corresponds to: $$ T(27)=2\cdot 10^{0}+8\cdot 10^{1}=82 \tag{27} $$ A worked example for an even input (e.g., $n=32$ ) is included in Appendix B.6. **Remark 2.1 (Arithmetic Transparency)** *The symbolic transition rules emulate classical base-10 arithmetic: - The odd case simulates $T(n)=3n+1$ via long multiplication with carry tracking. - The even case performs division by 2 through lookup and parity-based adjustments, analogous to manual division. Hence, the automaton replicates $T(n)$ precisely at the digit level.* 3 Correctness of Digitwise Transition Rules We now confirm that the unified digitwise rule introduced above faithfully emulates the arithmetic behavior of the Collatz function $T(n)$ . The symbolic update functions $\delta_{\text{even}}$ and $\delta_{\text{odd}}$ reproduce the digit-level base-10 representation of $T(n)∈\mathbb{N}$ exactly, including carry propagation and parity logic. These rules were derived directly from the standard algorithms for division and multiplication in positional notation [8]. **Remark 3.1** *The correctness of this digitwise formulation implies that the symbolic automaton is not an approximation of Collatz dynamics, but an exact reformulation over a finite-state digit system. This makes it suitable as a rigorous foundation for further formal analysis, including symbolic termination arguments.* 4 Finite-State Symbolic Convergence (Decimal FSM Model) We now formally prove that the symbolic Collatz automaton terminates in a unique 3-cycle for all $n∈\mathbb{N}^{+}$ . This establishes a fully symbolic convergence proof for the Collatz dynamics, given the numerical correctness of the digitwise emulation (cf. Section 2.2). The convergence behavior of the Collatz map has been the subject of extensive study, and is considered one of the most notorious open problems in elementary number theory [2]. 4.1 Symbolic Encoding and Digitwise Dynamics **Definition 4.1 (Symbolic State Representation)** *Let $n∈\mathbb{N}^{+}$ have decimal expansion $n=\sum_{i=0}^{L}r_{i}· 10^{i}$ , where $r_{i}∈\{0,...,9\}$ . We define its symbolic encoding as a sequence of digitwise states $$ s=[(r_{0},p_{0},c_{0}),\dots,(r_{L},p_{L},c_{L})]\in S^{L+1}, $$ where - $p_{i}:=r_{i+1}\bmod 2$ is the parity of the next digit (set to $0$ if $i=L$ ), - $c_{0}:=0$ and subsequent carry values $c_{i+1}$ are determined deterministically by the rules in Section 2.2.* **Definition 4.2 (Global Parity)** *Given a symbolic state sequence $s$ , we define its global parity by $\pi(s):=r_{0}\bmod 2$ . This determines whether the odd or even digitwise update rule applies.* **Theorem 4.3 (Correctness of Symbolic Emulation)** *For every $n∈\mathbb{N}^{+}$ , the symbolic encoding $s∈ S^{*}$ is uniquely defined, and the digitwise update rules $\delta_{\text{even}}$ and $\delta_{\text{odd}}$ reconstruct the next iterate $T(n)$ of the Collatz function via $$ T(n)=\sum_{i=0}^{L^{\prime}}r_{i}^{\prime}\cdot 10^{i},\quad\text{for some }L^{\prime}\in\{L-1,L,L+1\}, $$ where each digit $r_{i}^{\prime}$ is computed locally from $(r_{i},p_{i},c_{i})$ .* * Proof* The base-10 expansion of $n$ is unique, and both the parity values $p_{i}$ and carry values $c_{i}$ are deterministically assigned. The digitwise update functions $\delta_{i}$ compute the output digits $r_{i}^{\prime}$ in accordance with standard arithmetic. Therefore, $T(n)$ is reconstructed exactly from the symbolic sequence. ∎ **Remark 4.4** *The symbolic encoding map $\mathbb{N}^{+}\leftrightarrow S^{*}$ is bijective. Each encoding begins with $c_{0}=0$ , and the set of valid initial states is limited to the 20 combinations in $\{0,...,9\}×\{0,1\}×\{0\}$ .* 4.2 Automaton Structure and Terminal Cycle **Lemma 4.5 (Local Determinism)** *The digitwise update rules $$ \delta_{\text{even}}:S\to\{0,\dots,9\},\quad\delta_{\text{odd}}:S\to\{0,\dots,9\} $$ are total and deterministic. Carry values $c_{i}∈\{0,1,2\}$ are uniquely determined by recursive rules, and thus each symbolic transition is well-defined.* **Lemma 4.6 (Bounded Carry Propagation)** *For all $s_{i}∈ S$ , the carry values $c_{i}$ remain bounded: $c_{i}∈\{0,1,2\}$ . Odd Case: For worst-case digits $r_{i}=9$ and $c_{i}=2$ , the carry update (cf. Section 2.2) yields: $$ 3\cdot 9+2=29\quad\Rightarrow\quad c_{i+1}=\left\lfloor\frac{29}{10}\right\rfloor=2 $$ At the initial digit $i=0$ , with the additional constant term: $$ 3\cdot 9+1+0=28\quad\Rightarrow\quad c_{1}=\left\lfloor\frac{28}{10}\right\rfloor=2 $$ Even Case: Carries are computed using the parity of the next digit: $$ c_{i}:=\begin{cases}1&\text{if }r_{i+1}\bmod 2=1\\ 0&\text{otherwise}\end{cases} $$ Summary: In all cases, the carry values are bounded: $$ c_{i}\in\{0,1,2\}\quad\text{for all }i $$* **Lemma 4.7 (Finite Symbolic State Space)** *The symbolic state space is finite (see Table 5): $$ S:=\{0,\dots,9\}\times\{0,1\}\times\{0,1,2\},\quad\text{so }|S|=60 $$* **Remark 4.8 (Effective State Space is Reduced)** *While the total symbolic state space contains $|S|=60$ states, only $\sim 20$ of them occur repeatedly during the symbolic evolution. All states with $c>0$ are restricted to the first symbolic transition, and vanish immediately thereafter. Thus, the effective dynamical system unfolds almost entirely within the set $\{(r,p,0)\}$ .* <details> <summary>FSM20.png Details</summary>  ### Visual Description ## Directed Graph: State Transition Diagram ### Overview The image depicts a directed graph, also known as a state transition diagram. It consists of nodes (represented as pale yellow circles) labeled with numerical triples and directed edges (gray arrows) indicating transitions between these nodes. Some nodes have self-loops, indicating transitions back to themselves. ### Components/Axes * **Nodes:** Each node is a pale yellow circle labeled with a numerical triple in the format "X,Y,Z", where X, Y, and Z are integers. The nodes are positioned irregularly across the image. * **Edges:** The edges are gray arrows indicating the direction of the transition between nodes. * **Self-Loops:** Some nodes have arrows that loop back to themselves. ### Detailed Analysis or ### Content Details Here's a breakdown of the nodes and their connections: * **Node 0,0,0:** Located on the left side of the image. It has a self-loop. It has outgoing edges to nodes 1,0,0; 2,0,0; 4,1,0; 5,1,0; 8,0,0; 9,1,0. * **Node 0,1,0:** Located on the right side of the image. It has a self-loop. It has outgoing edges to nodes 1,0,0; 3,1,0; 5,0,0; 6,1,0; 7,1,0; 9,1,0. * **Node 1,0,0:** Located at the top-right of the image. It has a self-loop. It has outgoing edges to nodes 0,0,0; 0,1,0; 1,1,0; 2,0,0; 3,0,0; 4,0,0; 5,0,0; 6,0,0; 7,0,0; 8,0,0; 9,0,0. * **Node 1,1,0:** Located in the upper-center of the image. It has outgoing edges to nodes 0,0,0; 0,1,0; 3,1,0; 4,1,0; 5,0,0; 5,1,0; 6,0,0; 7,1,0. * **Node 2,0,0:** Located at the top-center of the image. It has outgoing edges to nodes 0,0,0; 1,0,0; 1,1,0; 3,0,0; 4,0,0; 4,1,0; 6,0,0; 7,0,0; 8,0,0. * **Node 2,1,0:** Located at the bottom-center of the image. It has outgoing edges to nodes 0,0,0; 0,1,0; 4,1,0; 6,1,0; 7,1,0; 8,0,0; 9,1,0. * **Node 3,0,0:** Located at the top-center of the image. It has outgoing edges to nodes 0,0,0; 1,0,0; 1,1,0; 4,0,0; 5,0,0; 6,0,0; 7,0,0; 8,0,0. * **Node 3,1,0:** Located in the center-right of the image. It has outgoing edges to nodes 0,0,0; 0,1,0; 1,1,0; 5,0,0; 5,1,0; 6,1,0; 7,1,0; 9,1,0. * **Node 4,0,0:** Located in the center of the image. It has outgoing edges to nodes 0,0,0; 1,0,0; 1,1,0; 4,1,0; 5,0,0; 6,0,0; 7,0,0; 8,0,0. * **Node 4,1,0:** Located on the left side of the image. It has outgoing edges to nodes 0,0,0; 1,1,0; 2,1,0; 5,1,0; 6,0,0; 8,0,0; 9,1,0. * **Node 5,0,0:** Located in the center-right of the image. It has outgoing edges to nodes 0,0,0; 0,1,0; 1,0,0; 1,1,0; 3,1,0; 4,0,0; 6,0,0; 7,1,0. * **Node 5,1,0:** Located in the center of the image. It has outgoing edges to nodes 0,0,0; 1,1,0; 3,1,0; 4,1,0; 6,0,0; 6,1,0; 8,0,0; 9,1,0. * **Node 6,0,0:** Located in the center of the image. It has outgoing edges to nodes 0,0,0; 1,0,0; 1,1,0; 4,0,0; 4,1,0; 5,0,0; 5,1,0; 7,0,0; 8,0,0. * **Node 6,1,0:** Located at the bottom-center of the image. It has outgoing edges to nodes 0,0,0; 0,1,0; 2,1,0; 3,1,0; 5,1,0; 7,1,0; 9,1,0. * **Node 7,0,0:** Located on the left side of the image. It has outgoing edges to nodes 0,0,0; 1,0,0; 2,0,0; 3,0,0; 4,0,0; 6,0,0; 8,0,0. * **Node 7,1,0:** Located at the bottom-right of the image. It has outgoing edges to nodes 0,0,0; 0,1,0; 1,1,0; 2,1,0; 3,1,0; 5,0,0; 6,1,0; 9,1,0. * **Node 8,0,0:** Located on the left side of the image. It has outgoing edges to nodes 0,0,0; 1,0,0; 2,0,0; 2,1,0; 3,0,0; 4,0,0; 4,1,0; 5,1,0; 6,0,0; 7,0,0. * **Node 8,1,0:** Located at the bottom-left of the image. It has a self-loop. It has outgoing edges to nodes 0,0,0; 2,1,0; 4,1,0; 6,1,0; 9,1,0. * **Node 9,0,0:** Located at the top of the image. It has outgoing edges to nodes 0,0,0; 1,0,0; 2,0,0; 3,0,0; 4,0,0; 6,0,0; 7,0,0; 8,0,0. * **Node 9,1,0:** Located at the bottom of the image. It has a self-loop. It has outgoing edges to nodes 0,0,0; 0,1,0; 2,1,0; 3,1,0; 4,1,0; 5,1,0; 6,1,0; 7,1,0; 8,1,0. ### Key Observations * Nodes 0,0,0; 0,1,0; 8,1,0; and 9,1,0 have self-loops. * Node 1,0,0 has outgoing edges to all other nodes. * Nodes 0,0,0 and 0,1,0 are the most common destination nodes. * The graph appears highly interconnected, with many nodes having multiple incoming and outgoing edges. ### Interpretation The diagram represents a state transition system where each node represents a state, and the arrows represent possible transitions between states. The numerical triples labeling the nodes likely represent some internal state variables or parameters. The self-loops indicate that the system can remain in the same state. The high degree of interconnectedness suggests that the system can transition between many different states. The diagram could represent a variety of systems, such as a Markov chain, a finite state machine, or a model of a physical process. Without further context, it is difficult to determine the specific meaning of the states and transitions. </details> Figure 1: Transition graph of the symbolic FSM restricted to the 20 active states. This subgraph contains the subset of symbolic triples $(r,p,c)$ that appear during actual Collatz iterations. The transitions encode local digitwise updates under the symbolic emulation of $T(n)$ . **Theorem 4.9 (Terminal Symbolic Behavior and Global Absorption)** *Let $S:=\{0,...,9\}×\{0,1\}×\{0,1,2\}$ denote the symbolic digit state space. 1. Every symbolic state $(r,p,c)∈ S\setminus\{(1,0,0),(2,0,0),(4,0,0)\}$ transitions deterministically to the null state $(0,0,0)$ under repeated application of the update rule $\delta$ . 1. The three states $(1,0,0)$ , $(2,0,0)$ , and $(4,0,0)$ form a unique terminal cycle: $$ (1,0,0)\to(4,0,0)\to(2,0,0)\to(1,0,0) $$ However, this cycle is only stable when it occurs at the least significant state position $s_{0}$ , and all higher positions $s_{i}$ with $i>0$ have already reached the null state $(0,0,0)$ . 1. If any higher digit $s_{k}^{(t)}≠(0,0,0)$ for some $k>0$ , then the terminal cycle is disrupted, and $s_{0}$ will continue evolving until the full collapse occurs. Thus, the symbolic Collatz system converges globally: every trajectory collapses into the null state in all but the least significant digit, which then cycles within the terminal loop.* 4.3 Local Symbolic Loops and Structural Collapse While analyzing the symbolic FSM, we observe recurring local loops involving certain digit states. Examples include: | | $\displaystyle(6,0,0)→(3,0,0)→(0,1,0)→(5,1,0)→(6,0,0),$ | | | --- | --- | --- | These finite cycles represent local oscillations induced by alternating parity patterns in the least significant state $s_{0}$ . However, they do not persist globally. Any activation of a higher digit (e.g., through carry overflow during odd steps) disrupts the cycle and leads to symbolic absorption into the null state $(0,0,0)$ . **Remark 4.10 (Local Cycles vs. Global Collapse)** *Finite loops in the symbolic automaton do not contradict global convergence. They are: - confined to the least significant state $s_{0}$ , - dependent on specific combinations of parity and carry values, - always disrupted once higher digits become active. Hence, these loops are structurally harmless and inherently short-lived.* **Corollary 4.11 (No Infinite Symbolic Loops Beyond the Terminal Cycle)** *The only globally persistent symbolic cycle is the terminal 3-cycle $$ (1,0,0)\rightarrow(4,0,0)\rightarrow(2,0,0)\rightarrow(1,0,0), $$ which survives exclusively at state position $s_{0}$ , after all higher digits have collapsed to $(0,0,0)$ . All other symbolic loops are local and inevitably collapse.* Loop-Driven Expansion and Role of $s_{0}$ . Although these symbolic loops are transient, they play a key role in triggering symbolic expansion. In particular: - Loops in $s_{0}$ often alternate between odd and even states, producing a high frequency of symbolic transitions. - This sustained alternation does not require activity in higher digits—parity alone controls the switching. - Over time, the rapid alternation can lead to carry buildup during odd steps (e.g., via $3r+c$ ), which eventually activates $s_{1}$ . - Once higher digits are active, the loop breaks, and the symbolic system expands temporarily before collapsing. **Remark 4.12 (Local timing and control element)** *The least significant state $s_{0}$ acts as a symbolic clock generator: its parity alternation determines the sequence of updates (odd vs. even), regardless of higher digit states. This rhythmic switching can sustain local loops, initiate expansion phases, and regulates the timing of symbolic contraction.* 4.4 Stability of the Null State **Lemma 4.13 (Null state is absorbing)** *Let $s_{i}^{(t)}=(0,0,0)$ for some $i>0$ , and assume that the incoming carry is zero, i.e., $c_{i}^{(t)}=0$ . Then $s_{i}^{(t+1)}=(0,0,0)$ . * Proof* With $r=0$ and $c=0$ we have both $3r+c=0$ (odd rule) and $\lfloor(r-c)/2\rfloor=0$ (even rule). Hence the symbolic state remains $(0,0,0)$ . ∎* **Lemma 4.14 (Digit absorption)** *For every digit position $i>0$ , there exists $T_{i}∈\mathbb{N}$ such that $s_{i}^{(t)}=(0,0,0)$ for all $t≥ T_{i}$ . * Proof* We proceed by induction on $i$ . Base case ( $i=1$ ): A newly created most significant digit can only arise through carry propagation during an odd step. By the update rules defined in Section 2.2, the only symbolic states that may appear in position $i=1$ are $(1,0,0)$ or $(2,0,0)$ , resulting from a maximal carry of $2$ . These states are part of the terminal cycle and collapse to $(0,0,0)$ in finitely many steps. Inductive step: Assume that $s_{i}^{(t)}=(0,0,0)$ and $c_{i}^{(t)}=0$ for all $t≥ T_{i}$ . Then, by Lemma 4.13, the next higher digit satisfies $s_{i+1}^{(t)}=(0,0,0)$ for all $t≥ T_{i}+1$ . Conclusion: All digit positions $i>0$ are eventually absorbed into the null state $(0,0,0)$ , and only the least significant digit remains dynamically active. ∎* **Theorem 4.15 (Finite symbolic support)** *For every symbolic trajectory $(s^{(t)})_{t∈\mathbb{N}}$ , there exists a time $T∈\mathbb{N}$ such that $$ s^{(t)}=[s_{0}^{(t)},(0,0,0),(0,0,0),\dots]\quad\text{for all }t\geq T. $$ Moreover, all transient higher-digit states are limited to the forms $(1,0,0)$ or $(2,0,0)$ .* * Proof* Immediate from Lemma 4.14. Combined with Theorem 4.9, this implies that after time $T$ , the complete symbolic configuration reduces to the 3-state cycle $$ (1,0,0)\to(4,0,0)\to(2,0,0)\to(1,0,0) $$ at the least significant state $s_{0}$ . ∎ 4.5 Digit Emergence via Carry Propagation New digit positions in the decimal representation of $T(n)$ can only emerge through carry overflow at the most significant digit, typically during odd transitions of the form $T(n)=3n+1$ . These overflows propagate leftward and may increment a previously zero digit, effectively increasing the overall length of the number. However, this form of digit growth is structurally limited. Carry values depend on the alternating parity structure of the Collatz sequence, which itself is governed by the presence of trailing $1$ -bits in the binary representation of the input. As these bits are progressively shifted out through repeated divisions, the system undergoes fewer odd transitions, and carry production diminishes accordingly. **Remark 4.16 (Carry-Driven Digit Growth Is Self-Limiting)** *Digit growth relies entirely on nonzero carry values originating from lower positions. Since such carries are only generated during odd steps—and these in turn depend on trailing $1$ s in the binary expansion—they cannot persist indefinitely. As a result, the number of digits can increase only temporarily and eventually returns to a stable size.* 4.6 Structural Constraint on the Peak Position We define the following key parameters of a symbolic Collatz orbit: - $t_{\text{end}}$ : total orbit length until convergence to 1, - $L_{\text{peak}}$ : maximum number of decimal digits observed during the orbit, - $t_{\text{peak}}$ : first step at which this maximum digit length is reached. From the definition of the effective symbolic decay time, we obtain: $$ T_{\text{eff}}:=\frac{t_{\text{end}}-t_{\text{peak}}}{L_{\text{peak}}-L_{\text{end}}} $$ In the standard case, where $L_{\text{end}}=1$ , this simplifies to: $$ T_{\text{eff}}:=\frac{t_{\text{end}}-t_{\text{peak}}}{L_{\text{peak}}-1} $$ Rearranging this inequality gives a direct bound on $t_{\text{peak}}$ : $$ t_{\text{peak}}=t_{\text{end}}-T_{\text{eff}}\cdot(L_{\text{peak}}-1) $$ Using the trivial lower bound $T_{\text{eff}}≥ 1$ yields: $$ t_{\text{peak}}\leq t_{\text{end}}-(L_{\text{peak}}-1) $$ And from the empirical estimate $T_{\text{eff}}≥\frac{t_{\text{end}}}{L_{\text{peak}}-1}-2$ , we finally derive the clean structural constraint: $$ t_{\text{peak}}\leq 2(L_{\text{peak}}-1) $$ Interpretation. The peak digit length is always reached sufficiently early in the orbit, specifically no later than twice the adjusted peak size. This constraint prevents excessive growth from occurring arbitrarily late in the trajectory and reflects an implicit structure in the digitwise evolution. Implication. The inequality reinforces the view that Collatz growth is globally constrained: even when large numeric peaks occur, the system compensates with a proportionally long collapse phase. Combined with the deterministic symbolic collapse (Theorem 4.8), this supports the hypothesis that infinite symbolic expansion is impossible. 4.7 Symbolic Termination via Ranking Function **Definition 4.17 (Cycle Distance Ranking)** *Let $\mathcal{C}⊂ S$ be the 3-cycle defined in Theorem 4.9. Define the symbolic ranking function $\varrho:S→\mathbb{N}$ by $$ \varrho(s):=\min\{k\in\mathbb{N}_{0}\mid\delta^{(k)}(s)\in\mathcal{C}\} $$* **Lemma 4.18 (Monotonic Descent)** *Every symbolic transition $\delta(s_{i})=s_{i+1}$ satisfies: $$ \varrho(s_{i+1})\leq\varrho(s_{i}), $$ with strict inequality unless $s_{i}∈\mathcal{C}$* **Theorem 4.19 (Symbolic Termination)** *All symbolic trajectories $(s_{0},s_{1},...)$ generated by iterated application of $\delta$ reach the terminal cycle $\mathcal{C}$ in finitely many steps.* * Proof* The function $\varrho$ is finite-valued and strictly decreases outside $\mathcal{C}$ . Thus, every sequence must eventually enter the cycle, and no infinite descent is possible. ∎ **Corollary 4.20 (Convergence of Collatz Iterates)** *For every $n∈\mathbb{N}^{+}$ , the symbolic trajectory of $n$ under $\delta$ terminates in the 3-cycle $\mathcal{C}$ , and hence the classical Collatz sequence enters the loop $4→ 2→ 1$ .* 5 Binary Structural Convergence This section presents a binary-level framework for analyzing Collatz convergence. We decompose trajectories into symbolic growth and decay phases based on the trailing bits in the binary encoding. By isolating multiplicative and divisive behavior through tail structure, we derive both empirical and deterministic measures of convergence pressure. Symbolic Block Formulation. We define the Collatz transformation in symbolic block form as follows: $$ T(n)=\begin{cases}T_{3}^{\mathrm{to}(n)}(n),&\text{(multiplicative phase)}\\ T_{2}^{\mathrm{tz}(n^{\prime})}(n^{\prime}),&\text{(divisive phase), where }n^{\prime}=T_{3}^{\mathrm{to}(n)}(n)\end{cases} $$ with: | | $\displaystyle T_{3}(n)$ | $\displaystyle:=\frac{3n+1}{2}\quad\text{(single odd step followed by division)},$ | | | --- | --- | --- | --- | Hence, each Collatz orbit proceeds in blocks of the form: $$ n\to T_{3}^{\mathrm{to}(n)}(n)=:n^{\prime}\to T_{2}^{\mathrm{tz}(n^{\prime})}(n^{\prime})=:n^{\prime\prime} $$ This decomposition emphasizes the symbolic alternation between expansion and contraction, structured by the binary tail. 5.1 Parity Alternation and Symbolic Lifetime Symbolic digit expansion under repeated Collatz steps requires alternating parity to activate both the multiplication and division transitions in a controlled fashion. This alternation arises from trailing $1$ s in the binary structure of the input: $$ \texttt{...1111}_{2}\quad\Rightarrow\quad\texttt{odd}\to\texttt{even}\to\texttt{odd}\to\cdots $$ Each even step shifts the binary suffix rightward, replacing $1$ s with $0$ s. As the tail of the binary representation flattens, parity changes become less frequent, and the system eventually enters a stable shrinking phase dominated by divisions. This behavior is illustrated by inputs such as $n=31=\texttt{0b11111}$ , which trigger long alternating sequences: $$ 31\to 94\to 47\to 142\to 71\to\dots $$ Each odd value is followed by an even one, until the bit suffix shifts: $$ \texttt{...111}\to\texttt{...1000}\to\texttt{...01000}\to\dots $$ **Remark 5.1 (Size Alone Does Not Imply Slowness)** *It is a common misconception that large input values necessarily require the most steps to reach the terminal cycle. While large numbers can produce long orbits, symbolic slowdown is more strongly correlated with the binary structure of the input. This was already observed by Lagarias [9], who showed that numbers of the form $2^{t}-1$ (e.g., $n=31=\texttt{0b11111}$ ) undergo $t$ consecutive odd steps before any division occurs. The trailing 1-bits in their binary encoding generate prolonged alternations, keeping symbolic length high despite numeric decrease. As a result, such inputs exhibit the longest symbolic lifetimes per digit, making them the true worst-case cases for symbolic contraction—not necessarily the largest inputs.* **Remark 5.2 (Binary Structure Governs Symbolic Lifetime)** *Even extremely large numbers, such as $10^{1000}-1$ , often exhibit shorter symbolic durations than structured binary inputs like $2^{t}-1$ . Thus, symbolic peak persistence depends more on bit entropy and parity alternation than numeric magnitude.* 5.2 Binary Tail Energy Model and Structural Regulation In addition to the symbolic digitwise automaton, we can view the convergence dynamics through the lens of binary structure, particularly the number of trailing zeros in the binary expansion of $n$ at each step. **Definition 5.3 (Binary Trailing Zero Count)** *Let $n∈\mathbb{N}^{+}$ . Define $\texttt{tz}(n)$ as the number of trailing $0$ -bits in the binary representation of $n$ : $$ \texttt{tz}(n):=\max\{k\in\mathbb{N}:2^{k}\mid n\} $$* This count reflects how many consecutive even divisions $T(n)$ can undergo before encountering another odd value. Interpretation. - When $\texttt{tz}(n)=0$ , the Collatz update $T(n)=3n+1$ applies, and produces an even result: $\texttt{tz}(T(n))≥ 1$ . - Each successive division by 2 reduces tz by 1, until it reaches zero again. This induces a natural alternation: $$ \texttt{tz}=0\Rightarrow\text{odd step (3n+1)}\quad\Rightarrow\quad\text{energy buildup} $$ $$ \texttt{tz}>0\Rightarrow\text{even steps}\quad\Rightarrow\quad\text{energy dissipation} $$ Energy Interpretation. We interpret tz as a symbolic "energy buffer": - $3n+1$ increases symbolic digit length and triggers carry propagation (cf. Section 2.2). - Even steps reduce both the binary length and symbolic digit complexity. - Thus, the system alternates between **growth** and **contraction**, but is globally biased toward contraction. Structural Implication. This view supports the convergence theorem (Theorem 4.15) from a binary angle: the symbolic system cannot grow arbitrarily, because each growth pulse from $3n+1$ is structurally paired with a trailing cascade of divisions that lower digit length and carry levels. **Remark 5.4 (Terminal Energy Depletion)** *Inputs like $n=2^{t}-1$ maximize symbolic alternation: their binary suffix consists of all $1$ s. This forces $\texttt{tz}=0$ for $t$ steps, leading to maximal symbolic expansion. But even these inputs eventually generate trailing zeros, and the system enters a decay phase.* **Remark 5.5 (Bit-Length Growth Under3​n+13n+1is Structurally Bounded)** *The step $T(n)=3n+1$ increases the binary length of $n$ by at most two bits. Specifically: $$ \text{If }n\in[2^{k},2^{k+1}),\text{ then }3n+1<3\cdot 2^{k+1}=2^{k+1}\cdot 3\Rightarrow\log_{2}(3n+1)<k+2 $$ Hence: $$ \Delta_{\text{bits}}(T(n))\leq 2 $$ This aligns with the decimal symbolic model, where a carry of at most 2 propagates during multiplication. Since each even step (division by 2) reduces the bit length by exactly one, the growth induced by any odd step is compensated after at most two divisions. This reinforces the interpretation that tz (the number of trailing zeros in binary) encodes a form of symbolic "energy" that the system discharges through repeated halving.* | 0 1 2 | 23 70 35 | 10111 1000110 100011 | 5 7 6 | 0 1 0 | | --- | --- | --- | --- | --- | | 3 | 106 | 1101010 | 7 | 1 | | 4 | 53 | 110101 | 6 | 0 | | 5 | 160 | 10100000 | 8 | 5 | | 6 | 80 | 1010000 | 7 | 4 | | 7 | 40 | 101000 | 6 | 3 | | 8 | 20 | 10100 | 5 | 2 | | 9 | 10 | 1010 | 4 | 1 | | 10 | 5 | 101 | 3 | 0 | | 11 | 16 | 10000 | 5 | 4 | | 12 | 8 | 1000 | 4 | 3 | | 13 | 4 | 100 | 3 | 2 | | 14 | 2 | 10 | 2 | 1 | | 15 | 1 | 1 | 1 | 0 | Table 3: Bit-level Collatz iteration for $n=23$ **Remark 5.6 (Bit-Level and Carry Coherence)** *It is no coincidence that both the binary bit-length and the symbolic carry values are bounded by 2 during odd steps (i.e., $3n+1$ ). This reflects a deep structural limit of the transformation: - Binary growth: Multiplication by 3 adds at most $\log_{2}(3)≈ 1.58$ bits. Thus, $$ \texttt{bitlen}(3n+1)\leq\texttt{bitlen}(n)+2 $$ - Symbolic carry: In the digitwise FSM, local updates $3r+c$ never exceed 29, so the propagated carry value satisfies $$ c^{\prime}=\left\lfloor\frac{3r+c}{10}\right\rfloor\leq 2\quad\text{for all }r\in\{0,\dots,9\},\,c\in\{0,1,2\} $$ This dual constraint—symbolic and binary—shows that the FSM encoding faithfully captures the core growth limits of the Collatz function. It is therefore not a numerical coincidence, but an algebraic invariant of the dynamics.* 5.3 Bit-Length Bounds for Classical Collatz Growth **Theorem 5.7 (Bit-Length Growth Bound for Odd Steps)** *Let $n∈\mathbb{N}^{+}$ , and let $\beta(n):=\lfloor\log_{2}(n)\rfloor+1$ denote the bit-length of $n$ . Then the Collatz update step $T(n)=3n+1$ , applied to odd $n$ , satisfies the bound $$ \beta(T(n))\leq\beta(n)+2. $$* * Proof* For all $n∈\mathbb{N}^{+}$ , we have: $$ 3n+1<4n. $$ Taking logarithms: $$ \log_{2}(3n+1)<\log_{2}(4n)=\log_{2}(n)+2. $$ Thus, using the bit-length function $\beta(n)=\lfloor\log_{2}(n)\rfloor+1$ , we get: $$ \beta(3n+1)=\lfloor\log_{2}(3n+1)\rfloor+1\leq\lfloor\log_{2}(n)+2\rfloor+1. $$ Now two cases: Case 1: $\log_{2}(n)∈\mathbb{Z}$ . Then $\lfloor\log_{2}(n)+2\rfloor=\log_{2}(n)+2$ , so $$ \beta(3n+1)\leq\log_{2}(n)+2+1=\beta(n)+2. $$ Case 2: $\log_{2}(n)∉\mathbb{Z}$ . Then $\lfloor\log_{2}(n)+2\rfloor=\lfloor\log_{2}(n)\rfloor+2$ , and again: $$ \beta(3n+1)\leq\lfloor\log_{2}(n)\rfloor+2+1=\beta(n)+2. $$ In both cases, the bit-length increases by at most 2. ∎ 5.4 Two-Phase Decomposition Starting from an odd number $n$ , the Collatz sequence can be decomposed into two symbolic phases: Phase 1 – Multiplicative Phase ( $T_{3}$ -block): $$ T_{3}(T_{3}(\dots T_{3}(n)))\quad\text{(applied }t_{o}(n)\text{ times)}, $$ This corresponds to a block of $t_{o}(n)$ successive applications of the transformation $T(n)=\frac{3n+1}{2}$ . Each such step tends to increase the bit-length by approximately $\log_{2}\left(\frac{3}{2}\right)$ . Phase 2 – Divisive Phase ( $T_{2}$ -block): Let $n^{\prime}$ be the result of the $T_{3}$ -block. Then: $$ T_{2}(T_{2}(\dots T_{2}(n^{\prime})))\quad\text{(applied }t_{z}(n^{\prime})\text{ times)}, $$ This phase corresponds to successive halving steps (i.e., $T(n)=\frac{n}{2}$ ), each reducing the bit-length by exactly one. 5.5 Interpretation of Terms - $t_{o}(n)$ : the number of trailing ones in the binary representation of $n$ - $n^{\prime}$ : the result of applying the transformation $T(n)=\frac{3n+1}{2}$ exactly $t_{o}(n)$ times - $t_{z}(n^{\prime})$ : the number of trailing zeros in the binary representation of $n^{\prime}$ 5.6 Symbolic Drift Function We define the symbolic drift function as $$ w(n):=\mathrm{to}(n)\cdot\log_{2}\left(\tfrac{3}{2}\right)-\mathrm{tz}(n^{\prime}), \tag{32} $$ where $\mathrm{to}(n)$ is the number of successive symbolic $T_{3}$ -steps starting from an odd number $n$ , and $\mathrm{tz}(n^{\prime})$ is the number of trailing zeros in binary of the result $n^{\prime}:=T_{3}^{\mathrm{to}(n)}(n)$ . This function measures the net symbolic bit-length change of a Collatz block and reflects the balance between expansion and contraction. Worst-case instance. For inputs of the form $n=2^{k}-1$ , we have $\mathrm{to}(n)=k$ and typically $\mathrm{tz}(n^{\prime})≥ k$ , yielding $$ w(n)\leq k\cdot\left(\log_{2}\left(\tfrac{3}{2}\right)-1\right)=k\cdot\log_{2}\left(\tfrac{3}{4}\right)<0, \tag{32} $$ matching the symbolic contraction constant $\log_{2}(3/4)≈-0.415$ noted by Tao. Empirical average. Simulations over all odd $n≤ 10^{6}$ yield: $$ \mathbb{E}[w(n)]\approx-0.83008, $$ confirming that symbolic contraction dominates on average. This value appears consistently across large input ranges and supports a universal convergence bias. <details> <summary>drift_histogram.png Details</summary>  ### Visual Description ## Histogram: Histogram of Drift Function w(n) for Odd n ≤ 10^6 ### Overview The image is a histogram displaying the distribution of a drift function w(n) for odd numbers n less than or equal to 10^6. The histogram shows the density of the drift function values, with a vertical red dashed line indicating the mean value. The distribution appears to be centered around zero, with a peak near the mean. ### Components/Axes * **Title:** Histogram of Drift Function w(n) for Odd n ≤ 10^6 * **X-axis:** w(n) = to(n) * log2(3/2) - tz(n') * Axis markers: -20, -15, -10, -5, 0, 5, 10 * **Y-axis:** Density * Axis markers: 0.0, 0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4, 1.6 * **Legend:** Located in the top-right corner. * Red dashed line: Mean ≈ -0.83009 ### Detailed Analysis * The histogram consists of light blue bars with black outlines. * The distribution is centered around zero, with the highest density near zero. * The red dashed line, representing the mean, is located at approximately -0.83009 on the x-axis. * The density values range from approximately 0 to 1.7. * The x-axis ranges from -20 to 10. * The bars are concentrated between -5 and 5. * The bars are very small outside the range of -5 to 5. ### Key Observations * The distribution is unimodal and centered near zero. * The mean is slightly negative, approximately -0.83009. * The distribution is skewed slightly to the left. * The majority of the data points are clustered around the mean. ### Interpretation The histogram visualizes the distribution of the drift function w(n) for odd numbers up to 10^6. The concentration of values around zero suggests that the drift function tends to produce values close to zero for most odd numbers within the specified range. The slight negative skew indicates that there are more values slightly below zero than slightly above zero. The mean value of approximately -0.83009 confirms this negative skew. The formula for w(n) involves the binary logarithm and functions to(n) and tz(n'), which likely contribute to the observed distribution. </details> Figure 2: Distribution of symbolic drift $w(n)$ for all odd $n≤ 10^{6}$ . The mean value (dashed red) confirms a consistent structural contraction. **Remark 5.8 (Gaussian Profile and Central Limit Behavior of Symbolic Drift)** *When computed over all odd inputs $n≤ 10^{6}$ , the symbolic drift function $w(n)$ exhibits a nearly Gaussian distribution centered around $\mathbb{E}[w(n)]≈-0.83$ . The empirical histogram shows a symmetric bell shape with skewness $≈-1.09$ and excess kurtosis $≈ 4.03$ , indicating mild left-skew and slightly heavier tails compared to the standard normal curve. This behavior is particularly remarkable given that $w(n)$ is defined through purely deterministic symbolic transformations involving $\mathrm{to}(n)$ and $\mathrm{tz}(n^{\prime})$ . Despite their discrete origin, these terms aggregate statistically as if governed by the central limit theorem: they act like weakly dependent components whose combined effect produces a continuous, tightly concentrated distribution. The resulting normality highlights an emergent regularity within symbolic Collatz dynamics – a convergence structure that is not only average-negative but also statistically regulated. It supports the interpretation of $w(n)$ as a structural invariant rather than a mere empirical artifact.* <details> <summary>qqplot.png Details</summary>  ### Visual Description ## Q-Q Plot: w(n) vs. Normal Distribution ### Overview The image is a Q-Q (quantile-quantile) plot comparing the distribution of a variable w(n) against a normal distribution with a mean (μ) of -0.83 and a standard deviation (σ) of 1.64. The plot displays ordered values of w(n) against theoretical quantiles from the specified normal distribution. The blue dots represent the data points, and the red line represents the expected distribution if w(n) were perfectly normally distributed. ### Components/Axes * **Title:** Q-Q Plot of w(n) vs. Normal(μ = -0.83, σ = 1.64) * **X-axis:** Theoretical quantiles, ranging from approximately -8 to 6, with tick marks at every increment of 2. * **Y-axis:** Ordered Values, ranging from -20 to 10, with tick marks at every increment of 5. * **Data Points:** Blue dots representing the quantiles of w(n). * **Reference Line:** A red line representing the theoretical normal distribution. ### Detailed Analysis * **X-Axis (Theoretical Quantiles):** * -8 * -6 * -4 * -2 * 0 * 2 * 4 * 6 * **Y-Axis (Ordered Values):** * -20 * -15 * -10 * -5 * 0 * 5 * 10 * **Data Points (Blue):** * The blue data points represent the ordered values of w(n). * At the lower end (left side of the plot), the blue dots deviate significantly below the red line, indicating that the lower tail of w(n) has more extreme values than the normal distribution. * In the middle section (around the theoretical quantiles of -2 to 2), the blue dots are closer to the red line, suggesting a better fit to the normal distribution in this range. * At the upper end (right side of the plot), the blue dots are slightly above the red line, indicating that the upper tail of w(n) has slightly higher values than the normal distribution. * **Reference Line (Red):** * The red line represents the expected distribution if w(n) followed a normal distribution with μ = -0.83 and σ = 1.64. * The red line starts at approximately (-8, -8) and ends at approximately (6, 6). ### Key Observations * The distribution of w(n) deviates from the normal distribution, especially in the tails. * The lower tail of w(n) is heavier than the normal distribution, as indicated by the blue dots falling below the red line on the left side of the plot. * The upper tail of w(n) is slightly heavier than the normal distribution, as indicated by the blue dots falling slightly above the red line on the right side of the plot. * The central part of the distribution of w(n) is closer to the normal distribution. ### Interpretation The Q-Q plot suggests that the variable w(n) is not perfectly normally distributed. The deviations in the tails indicate that w(n) has a different distribution shape, with heavier tails than the normal distribution with μ = -0.83 and σ = 1.64. This means that extreme values are more frequent in w(n) than would be expected in a normal distribution with the specified parameters. The plot is useful for assessing the normality assumption in statistical analyses and for identifying potential outliers or deviations from normality. </details> Figure 3: Q–Q plot comparing the empirical distribution of the symbolic drift function $w(n)$ (for odd $n≤ 10^{6}$ ) against a normal distribution with $\mu=-0.83$ , $\sigma≈ 1.638$ . The close alignment confirms near-Gaussian behavior. **Remark 5.9 (Q–Q-Plot and Empirical Normality of the Drift)** *To empirically verify the near-normality of the drift distribution $w(n)$ , we compared it to a Gaussian distribution $\mathcal{N}(\mu=-0.83,\sigma≈ 1.638)$ using a quantile–quantile (Q–Q) plot. The empirical quantiles align closely with the theoretical normal quantiles, particularly in the central region of the distribution. Minor deviations near the tails confirm the slightly leptokurtic profile observed earlier (kurtosis $≈ 4.03$ ) and a mild left skew (skewness $≈-1.09$ ). Nevertheless, the overall fit is strong, confirming that the symbolic drift behaves statistically like a Gaussian-distributed variable. This alignment reinforces the interpretation of $w(n)$ as an emergent statistical invariant: a deterministic but stochastically behaving quantity, supporting the idea that the symbolic Collatz dynamics simulate a central limit phenomenon without requiring randomness.* **Remark 5.10 (Emergent Structure Behind Probabilistic Success)** *The near-Gaussian behavior of the symbolic drift function $w(n)$ , despite its fully deterministic definition, suggests that the statistical patterns observed in previous stochastic or heuristic approaches may not arise from inherent randomness — but rather from the structured composition of symbolic Collatz dynamics itself. This perspective reframes the effectiveness of probabilistic models (e.g., via random walks or ergodic arguments) not as evidence for randomness in the system, but as a reflection of underlying regularities that mimic stochastic behavior. In this light, previous results may have succeeded not by modeling true uncertainty, but by coincidentally aligning with emergent statistical invariants of a deterministic process.* Structural explanation. This contraction is not accidental but structurally determined by binary properties of the input. Specifically: 1. Trailing-one expectation. For odd $n$ , the number of trailing binary ones satisfies: $$ \mathbb{E}[\mathrm{to}(n)]=\sum_{k=1}^{\infty}k\cdot\left(\frac{1}{2}\right)^{k}=2 \tag{12} $$ 1. Decay behavior. Empirically, the expansion result $n^{\prime}$ satisfies: $$ \mathbb{E}[\mathrm{tz}(n^{\prime})]\approx 2.00 $$ Thus, both phases—symbolic expansion and decay—have symmetric average length. 1. Resulting contraction. Substituting into the drift formula gives: $$ \mathbb{E}[w(n)]\approx 2\cdot\log_{2}\left(\tfrac{3}{2}\right)-2=\log_{2}\left(\tfrac{9}{16}\right)\approx-0.83008 \tag{32} $$ Significance. This value represents a structural invariant of the symbolic Collatz system. Each block enforces net bit-length loss, making long-term expansion impossible. **Remark 5.11 (Role of Division Steps)** *In symbolic Collatz blocks, the halving steps $T_{2}(n)=\frac{n}{2}$ play a strictly subtractive role. Each application removes one trailing binary zero without altering internal structure: $$ \text{Bin}(T_{2}(n))=\text{Bin}(n)\text{ with the final }0\text{ removed}. $$ Hence, $\mathrm{tz}(n^{\prime})$ contributes a pure contraction term in the drift function, structurally balancing the additive impact of $T_{3}$ -steps.* 5.7 Illustrative Example: Symbolic Block Decomposition for $n=15$ We demonstrate the symbolic block decomposition for the Collatz orbit starting at $n=15$ , using the alternation structure defined by trailing ones (to) and trailing zeros (tz). Full Orbit (values only): $$ 15\to 46\to 23\to 70\to 35\to 106\to 53\to 160\to 80\to 40\to 20\to 10\to 5\to 16\to 8\to 4\to 2\to 1 $$ Block Decomposition (step-based): Each step refers to a single transition (an arrow $a→ b$ ). The value $n^{\prime}$ at the end of a $T_{3}$ -block is defined as the **final value reached before switching to a divisive phase**. The number of divisions is then governed by $\texttt{tz}(n^{\prime})$ . - Block 1 – $T_{3}$ (8 steps): Triggered by $\texttt{to}(15)=4$ , which leads to 4 symbolic $T_{3}$ cycles (each consisting of a mul3 and a div2): $$ 15\to 46\to 23\to 70\to 35\to 106\to 53\to 160\to 80 $$ The final value is $n^{\prime}=80$ , so the next block will contain exactly $\texttt{tz}(80)=4$ halving steps. - Block 2 – $T_{2}$ (4 steps): $$ 80\to 40\to 20\to 10\to 5 $$ These are pure division steps, ending when $\texttt{to}(5)=1$ triggers a new symbolic cycle. - Block 3 – $T_{3}$ (2 steps): $$ 5\to 16\to 8 $$ Based on $\texttt{to}(5)=1$ , we apply one $T_{3}$ cycle. - Block 4 – $T_{2}$ (3 steps): $$ 8\to 4\to 2\to 1 $$ Even though $\texttt{tz}(8)=3$ , the orbit ends after exactly 3 division steps. Summary: $$ \boxed{T_{3}\text{-Block (8 steps)}}\;\to\;\boxed{T_{2}\text{-Block (4 steps)}}\;\to\;\boxed{T_{3}\text{-Block (2 steps)}}\;\to\;\boxed{T_{2}\text{-Block (3 steps)}} $$ **Remark 5.12 (Precise Phase Boundaries)** *The transition from a $T_{3}$ to a $T_{2}$ block occurs after the final result of the last $T_{3}$ step has been reached. This means that $n^{\prime}$ —used to determine the next tz —is defined as the terminal value of the $T_{3}$ -phase. In this case: $n^{\prime}=80$ , and $\texttt{tz}(80)=4$ .* 5.8 Symbolic Energy Function and Deterministic Convergence To move from empirical trends to a formal descent guarantee, we define a symbolic potential function that strictly decreases along Collatz trajectories. Let $n_{0}$ denote the initial value of a given trajectory. We define: $$ f(n):=\frac{\log_{2}(n)}{\log_{2}(n_{0})}+\mathrm{to}(n)-\mathrm{tz}(n), $$ where $\mathrm{to}(n)$ is the number of trailing ones in the binary representation of $n$ , and $\mathrm{tz}(n)$ the number of trailing zeros. This function captures both the relative magnitude of the current iterate and its symbolic structure. It contracts whenever a symbolic block—comprising $\mathrm{to}(n)$ many $T_{3}$ -steps followed by $\mathrm{tz}(n^{\prime})$ divisions—has net negative drift. <details> <summary>deltaf-plot.png Details</summary>  ### Visual Description ## Scatter Plot: Delta f vs n ### Overview The image is a scatter plot showing the relationship between two variables, delta f (Δf) on the y-axis and n on the x-axis. The plot contains multiple data series, all represented by orange points. The data series appear to converge to distinct horizontal lines as 'n' increases. A red dashed line is present at y=0. ### Components/Axes * **X-axis:** Labeled "n", with a scale from 0 to 10000, incrementing by 2000. * **Y-axis:** Labeled "Δf", with a scale from -16 to 0, incrementing by 2. * **Data Series:** Multiple data series are plotted, all in orange. * **Reference Line:** A horizontal dashed red line is present at Δf = 0. * **Grid:** The plot has a light gray grid. ### Detailed Analysis The plot contains several distinct data series, all represented by orange points. Each series appears to converge to a specific horizontal level as 'n' increases. * **Series 1 (Topmost):** This series starts around Δf = -2 and quickly converges to a horizontal line at approximately Δf = -2. * **Series 2:** This series starts around Δf = -3 and converges to a horizontal line at approximately Δf = -3. * **Series 3:** This series starts around Δf = -4 and converges to a horizontal line at approximately Δf = -4. * **Series 4:** This series starts around Δf = -5 and converges to a horizontal line at approximately Δf = -5. * **Series 5:** This series starts around Δf = -6 and converges to a horizontal line at approximately Δf = -6. * **Series 6:** This series starts around Δf = -7 and converges to a horizontal line at approximately Δf = -7. * **Series 7:** This series starts around Δf = -8 and converges to a horizontal line at approximately Δf = -8. * **Series 8:** This series starts around Δf = -9 and converges to a horizontal line at approximately Δf = -9. * **Series 9:** This series starts around Δf = -10 and converges to a horizontal line at approximately Δf = -10. * **Series 10:** This series starts around Δf = -11 and converges to a horizontal line at approximately Δf = -11. * **Series 11:** This series starts around Δf = -12 and converges to a horizontal line at approximately Δf = -12. * **Series 12:** This series starts around Δf = -13 and converges to a horizontal line at approximately Δf = -13. * **Series 13:** This series starts around Δf = -14 and converges to a horizontal line at approximately Δf = -14. * **Series 14:** This series starts around Δf = -15 and converges to a horizontal line at approximately Δf = -15. ### Key Observations * The data series exhibit a clear trend of converging to distinct horizontal levels as 'n' increases. * The horizontal levels are spaced approximately one unit apart on the Δf axis. * The convergence appears to happen more rapidly for the series closer to Δf = 0. * The red dashed line at Δf = 0 serves as a reference point. ### Interpretation The plot suggests that as 'n' increases, the value of Δf for each series approaches a specific, stable value. The distinct horizontal levels indicate that the system being modeled may have discrete states or stable configurations. The rapid convergence for series closer to Δf = 0 might indicate a stronger stabilizing force or faster relaxation towards equilibrium for those states. The plot visualizes the relationship between 'n' and Δf, demonstrating how 'n' influences the stability or convergence of Δf towards specific values. </details> Figure 4: Change in the symbolic energy function over the range $n∈[2,10^{4}]$ for all inputs with $\mathrm{to}(n)>0$ . Each point represents the difference $\Delta f=f(T^{\mathrm{to}(n)}(n))-f(n)$ . The consistent negative values confirm that symbolic Collatz blocks induce strict contraction of the ranking function. This supports deterministic convergence along structured trajectories. Descent Property. Let $k:=\mathrm{to}(n)$ , $m:=\mathrm{tz}(n^{\prime})$ , and $n^{\prime}:=T_{3}^{k}(n)$ . Then: $$ f(T^{k}(n))-f(n)=\frac{\log_{2}(n^{\prime})-\log_{2}(n)}{\log_{2}(n_{0})}-(k+m) $$ Using the estimate $n^{\prime}≤(3/2)^{k}· n$ , we obtain: $$ f(T^{k}(n))-f(n)\leq\frac{k\cdot\log_{2}(3/2)}{\log_{2}(n_{0})}-(k+m) $$ Setting $\log_{2}(n_{0})=1$ for normalization, we recover the symbolic drift inequality: $$ 1+\frac{\mathrm{tz}(n^{\prime})}{\mathrm{to}(n)}>\log_{2}\left(\tfrac{3}{2}\right) \tag{32} $$ which always holds, since $\mathrm{to}(n)≥ 1$ and $\mathrm{tz}(n^{\prime})≥ 0$ . **Lemma 5.13 (Symbolic Energy Decrease)** *For all odd $n$ with $\mathrm{to}(n)>0$ , the symbolic energy function strictly decreases: $$ f(T^{\mathrm{to}(n)}(n))<f(n) $$* Conclusion. The symbolic potential function $f(n)$ provides a deterministic ranking that decreases blockwise and is bounded from below. Therefore, the symbolic Collatz system terminates without statistical assumptions. Each block enforces bit-level decay and guarantees symbolic contraction. **Remark 5.14 (Absolute Drift Inequality)** *The inequality $$ 1+\frac{\mathrm{tz}(n^{\prime})}{\mathrm{to}(n)}>\log_{2}\left(\tfrac{3}{2}\right) \tag{32} $$ is not a statistical average but a symbolic invariant of every odd input.* **Remark 5.15 (Historical Note on the Drift Constant)** *The symbolic drift constant $$ \log_{2}\left(\tfrac{3}{2}\right)-1=\log_{2}\left(\tfrac{3}{4}\right)\approx-0.415 \tag{32} $$ has appeared in earlier work: - Terras and Lagarias observed it in average-case and density models for Collatz iteration. - Tao derived it in a probabilistic setting using stochastic dynamics. However, the expression $$ \log_{2}\left(\tfrac{3}{2}\right)-1 \tag{32} $$ now admits a structural interpretation: one symbolic growth ( $\log_{2}(3/2)$ ) followed by one contraction step (division by 2). This alternation explains the convergence behavior not through probability, but as a deterministic invariant encoded in the FSM.* 5.9 Connection to Decimal FSM While the drift and energy functions are derived purely from the binary representation of $n$ , they align structurally with the decimal FSM model. - Both frameworks reflect the same growth–decay duality: odd steps expand symbolic size, even steps contract it. - The FSM enforces bounded carries ( $c∈\{0,1,2\}$ ) during symbolic multiplication, which corresponds to a maximal bit-length increase of 2 under $3n+1$ . - The convergence theorem for the FSM (Theorem 4.15) is structurally mirrored by the symbolic drift inequality: $$ 1+\frac{\mathrm{tz}(n^{\prime})}{\mathrm{to}(n)}>\log_{2}\left(\tfrac{3}{2}\right), \tag{32} $$ which guarantees descent in the binary energy function $f(n)$ . This approach provides a new structural lens for analyzing recursive functions. Rather than relying on numerical growth bounds, it translates dynamics into a finite symbolic domain, making it amenable to mechanized reasoning. While the main construction operates over base-10 representations, the method itself is not inherently decimal: symbolic emulation has also been demonstrated for binary encodings using adapted FSM variants. Two such binary FSM models are outlined in Appendix E, showing how the symbolic transition idea extends beyond decimal digits. Whether this framework generalizes to broader function classes or arbitrary number bases remains an open question. 6 Limitations and Formal Scope The symbolic Collatz framework developed in this paper replaces classical analytic or probabilistic strategies with a fully deterministic and constructive model. The digitwise automata introduced in Section 2.2 emulate the Collatz function $T(n)$ through local updates on finite symbolic states. - All symbolic operations — digit parity, carry propagation, and the local update rules $\delta_{\text{odd}}$ , $\delta_{\text{even}}$ — are elementary and primitive recursive. The entire system is, in principle, representable within first-order Peano Arithmetic (PA) or bounded arithmetic. - The correctness of the digitwise emulation (Theorem 4.3) ensures that symbolic steps correspond exactly to Collatz updates. While this equivalence has not yet been formally verified in a proof assistant such as Coq or Lean, the symbolic definitions are fully explicit and mechanization-ready. - The convergence proof (Theorem 4.15) is conditional on the correctness of the encoding. Once this correspondence is formalized, the result becomes provable without reference to classical number theory or analytic bounds. This symbolic approach offers a new structural lens for analyzing recursive functions. Rather than relying on global numerical estimates, it translates dynamics into a finite symbolic domain with provably bounded behavior, making it amenable to automated verification. Although the main construction operates in decimal (base-10), the method is not inherently tied to this number system. In Appendix E, we describe two alternative FSM variants built for binary (base-2) inputs. These models follow the same symbolic principles, but require modified local update rules due to the differences in base arithmetic: - Carry propagation behaves differently in binary and leads to a reduced symbolic state space. - Parity-based transitions simplify, but the symbolic encoding must account for bitwise alignment and mod-2 carries. - As in the decimal case, the global arithmetic behavior of $T(n)$ is reproduced through strictly local symbolic transitions. Finally, although our framework was developed for the classical Collatz function, it generalizes naturally to arbitrary affine maps $T(n)=an+b$ . As shown in Section LABEL:sec:anb-generalization, the same digitwise mechanism can emulate such functions via adjusted local rules. This opens the door to broader classes of recursively defined systems whose dynamics can be captured symbolically. 7 Discussion and Future Directions The symbolic finite-state model introduced in this work offers a new structural framework for analyzing arithmetic dynamics through local, digitwise transformations. While originally constructed for the classical Collatz function, its underlying architecture—based on parity-aware carry propagation—is fundamentally extensible. Generalization Potential. The digitwise mechanism extends naturally to affine maps of the form $T(n)=an+b$ , as long as the coefficients are compatible with local carry arithmetic. Appendix LABEL:sec:anb-generalization outlines a generalized transition scheme for such updates. This suggests the possibility of a broader symbolic calculus for integer recursions, enabling new finite-state models beyond the Collatz case. Binary Extensions and Structural Insights. In addition to the decimal representation, binary FSM variants (Appendix E) implement the same symbolic principles in base 2. While these require different transition rules, they retain the key idea: reconstructing global behavior through strictly local symbolic updates. When combined with the drift and ranking functions of Section 5, this binary view provides a structural explanation for convergence, independent of numerical bounds. Open Problems. The finite-state framework opens several directions for further exploration: - Can symbolic automata be constructed for other unsolved problems in arithmetic dynamics? - How do symbolic trajectories behave under variations of $a$ and $b$ in affine maps $T(n)=an+b$ ? - Can symbolic convergence principles be extended to non-affine or piecewise-defined recursive functions? While base changes (e.g., decimal to binary) alter local update rules, the overall convergence structure appears invariant—pointing to a deeper algebraic principle that merits further investigation. Claim of Novelty. To the best of the author’s knowledge, this is the first model that emulates Collatz dynamics via explicit symbolic digit triples $(r,p,c)$ , deterministic local transitions, and bounded carry propagation within a finite-state system. Unlike heuristic or analytic approaches, the present framework offers a constructive reformulation of the problem, enabling formal convergence proofs and laying the groundwork for mechanized verification and broader generalization. 8 Conclusion and Structural Insights We have introduced a finite-state symbolic automaton that emulates the Collatz map $T(n)$ through strictly local digitwise transformations. Each decimal digit is represented by a symbolic triple $(r,p,c)$ , encoding the digit value, the parity of the next digit, and a bounded carry. These local updates—total, deterministic, and primitive recursive—collectively reconstruct the full Collatz iteration without global arithmetic, enabling structural convergence proofs within a finite symbolic space. Symbolic Convergence. The automaton enforces termination by collapsing all but the least significant symbolic digit into the null state $(0,0,0)$ . Once only $s_{0}$ remains active, the system enters a unique 3-cycle $(4,0,0)→(2,0,0)→(1,0,0)$ , structurally mimicking the classical loop $4→ 2→ 1$ . Convergence is guaranteed by bounded carry propagation and digit-level absorption, showing that the automaton supports only finitely many dynamically active states throughout any trajectory. Binary Interpretation. To complement the symbolic model, we introduced a binary framework that analyzes convergence through the number of trailing ones and zeros in binary expansion. This yields a structural drift function and an energy ranking potential that contract deterministically across symbolic blocks. Odd steps $(3n+1)/2$ increase symbolic complexity and bit length, while halving steps remove trailing zeros without altering internal structure. Crucially, both the binary bit-length and the symbolic carries are strictly bounded—odd steps increase size by at most two bits, and symbolic carries never exceed two. This confirms a fundamental dissipative property embedded in the dynamics. Dual Perspective. Taken together, the symbolic and binary views reveal that Collatz convergence is not merely numerical but deeply structural: a self-limiting alternation between symbolic growth and digit-level decay. The apparent complexity of Collatz trajectories arises from a highly constrained interplay of parity, position, and bounded carry logic—far from chaotic, the process behaves like a regulated symbolic system with finite entropy. Outlook. This framework opens a new pathway for analyzing recursive arithmetic functions via finite-state models. Future work may: - mechanize the symbolic encoding in proof assistants such as Coq or Lean, - generalize the automaton to other affine maps $T(n)=an+b$ with symbolic carry logic, - explore base-2 and modular variants with adapted symbolic states, - or design related symbolic dynamics for other open problems in arithmetic iteration. The symbolic Collatz FSM thus recasts a historically intractable conjecture into a verifiable, locally deterministic system. By shifting the focus from numerical iteration to symbolic structure, it reveals a new finite-state foundation for convergence—and opens the door to further exploration at the interface of number theory, logic, and automata. Acknowledgements This work was developed independently. I would like to acknowledge the assistance of OpenAI’s language model (ChatGPT-4), which supported the writing process by helping with linguistic refinement, formal structuring, and programming tasks related to the generation of illustrative graphics. All mathematical reasoning, results, and conclusions are solely my own. License: This work is licensed under a CC BY-NC-ND 4.0 license. References - [1] Jeffrey C. Lagarias. The 3x+1 problem: An annotated bibliography (1963–1999). arXiv:math/0309224, 2003. https://arxiv.org/abs/math/0309224. - [2] Jeffrey C. Lagarias. The 3x+1 problem: An overview. arXiv preprint arXiv:2111.02635, 2021. https://arxiv.org/abs/2111.02635. - [3] Jeffrey C. Lagarias. The 3x+1 problem: An annotated bibliography ii (2000–2009). arXiv:math/0608208, 2006. https://arxiv.org/abs/math/0608208. - [4] Terence Tao. Almost all orbits of the collatz map attain almost bounded values. Forum of Mathematics, Pi, 8:e14, 2020. https://arxiv.org/abs/1909.03562. - [5] Jeffrey C. Lagarias and Alan Weiss. The 3x+1 problem: Two stochastic models. Annals of Applied Probability, 2(1):229–261, 1992. - [6] Kenneth H. Rosen. Discrete Mathematics and Its Applications. McGraw-Hill, 7th edition, 2012. - [7] Michael Sipser. Introduction to the Theory of Computation. Cengage Learning, 2nd edition, 2005. - [8] Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, 3rd edition, 1997. - [9] Jeffrey C. Lagarias. The 3x+1 problem and its generalizations. The American Mathematical Monthly, 92(1):3–23, 1985. Appendix A Formal and Computational Details This appendix provides the formal underpinnings and supplementary computations that support the symbolic Collatz model developed in the main text. It contains: - a generalization of the digitwise transition mechanism to arbitrary affine functions $T(n)=an+b$ , - step-by-step symbolic evaluations for selected input values, - a worked example of symbolic state evolution along a full Collatz trajectory, and - the complete transition table of the finite-state machine governing symbolic digit dynamics. All constructions are presented in a primitive recursive form and are fully compatible with the deterministic automaton architecture introduced in Section 2.2. Appendix B Symbolic Digitwise Model for General $an+b$ The digitwise update mechanism developed for the Collatz map $T(n)=3n+1$ generalizes naturally to arbitrary affine functions of the form $$ T(n)=a\cdot n+b, $$ with $a,b∈\mathbb{N}$ . This section describes how such functions can be emulated through purely local digit-level transformations. Two distinct strategies are available, depending on the size of the parameters $a$ and $b$ : B.1 Digitwise Transition Rule Let $n=\sum_{i=0}^{L}r_{i}· 10^{i}$ be the decimal expansion of $n$ , and define an initial carry $c_{0}:=0$ . There are two strategies for computing $T(n)=a· n+b$ symbolically: (1) Simplified Rule for Small $a,b$ : If $a<10$ and $b<10$ , then the digitwise update can be performed directly during the multiplication phase: $$ r_{i}^{\prime}:=\begin{cases}(a\cdot r_{i}+b+c_{i})\bmod 10&\text{if }i=0,\\ (a\cdot r_{i}+c_{i})\bmod 10&\text{if }i>0,\end{cases}\qquad c_{i+1}:=\begin{cases}\left\lfloor\dfrac{a\cdot r_{i}+b+c_{i}}{10}\right\rfloor&\text{if }i=0,\\ \left\lfloor\dfrac{a\cdot r_{i}+c_{i}}{10}\right\rfloor&\text{if }i>0.\end{cases} $$ This method is valid only for single-digit constants $b$ . (2) General Two-Phase Method (Fully Correct): For arbitrary $a,b∈\mathbb{N}$ , the symbolic computation must be performed in two separate phases: 1. Multiplication: Compute $a· n$ digitwise with carry propagation: $$ r_{i}^{\prime}:=(a\cdot r_{i}+c_{i})\bmod 10,\qquad c_{i+1}:=\left\lfloor\frac{a\cdot r_{i}+c_{i}}{10}\right\rfloor $$ 1. Addition: Perform a standard digitwise addition of $b$ to the result of the multiplication, including carry. This ensures correctness for all $a,b∈\mathbb{N}$ . B.2 Alternative Formulation The same transformation can be written as: $$ T(n)=an+b=\left(\sum_{i=0}^{L}ar_{i}\cdot 10^{i}\right)+b, $$ which corresponds to multiplying each digit $r_{i}$ by $a$ , applying carry propagation, and finally injecting the constant term $b$ at the least significant position. **Remark B.1 (Full Addition of𝒃b)** *For general $b∈\mathbb{N}$ , the additive term should be treated as a separate value added to $a· n$ after digitwise multiplication and carry propagation. The simplified digitwise injection of $b$ at the least significant digit (i.e., within $r_{0}^{\prime}$ ) remains valid only if $b<10$ . For larger $b$ , a full digitwise addition must follow the multiplication phase.* B.3 Bounded Carry and Finite State Space The carry values remain bounded due to the fixed-digit range: $$ c_{\max}\leq\left\lfloor\frac{9a+b}{10}\right\rfloor, $$ so the symbolic state space remains finite: $$ S_{(a,b)}:=\{0,\dots,9\}\times\{0,1\}\times\{0,\dots,c_{\max}\}. $$ B.4 Interpretation This generalized rule preserves the core structure of the symbolic Collatz system: digitwise updates, carry propagation, and optional parity tagging. It allows the symbolic emulation of arbitrary affine maps of the form $T(n)=an+b$ via finite-state digit dynamics in base 10. In this light, the classical Collatz rule $T(n)=3n+1$ becomes a special case of the more general symbolic framework. The model thus extends beyond Collatz-specific behavior and opens the door to structural analysis of other recursive systems governed by similar local rules. B.5 Generalized Symbolic Drift in $T_{a,1}$ -Systems **Definition B.2 (Symbolic Block Drift)** *Let $T_{a,1}(n):=\frac{an+1}{2^{k}}$ , where $k:=\mathrm{tz}(an+1)$ . We define the symbolic drift of a full Collatz block (growth–decay phase) as: $$ w_{a,1}(n):=\mathrm{to}(n)\cdot\log_{2}\left(\frac{a}{2}\right)-\mathrm{tz}\left(T_{3}^{\mathrm{to}(n)}(n)\right) $$ where: - $\mathrm{to}(n)$ : number of trailing ones in the binary expansion of $n$ , - $T_{3}(n):=\frac{an+1}{2}$ : odd-case transformation, - $T_{3}^{\mathrm{to}(n)}(n)$ : value after applying $\mathrm{to}(n)$ many $T_{3}$ -steps, - $\mathrm{tz}(·)$ : number of trailing zeros (i.e., maximal halving steps following the expansion).* **Remark B.3 (Structural Contraction Criterion)** *The drift $w_{a,1}(n)$ measures the bit-length change of a symbolic block. Averaging over all odd inputs yields: $$ \mathbb{E}[w_{a,1}(n)]<0\quad\Longrightarrow\quad\text{global symbolic contraction}. $$ This occurs if the trailing-zero decay outweighs the logarithmic growth from repeated $T_{3}$ -steps.* <details> <summary>symbolic_drift_vs_log_fit.png Details</summary>  ### Visual Description ## Chart: Comparison of Symbolic Drift vs. Logarithmic Approximation ### Overview The image is a line chart comparing empirical data with a theoretical logarithmic approximation. The x-axis represents 'a (odd)' ranging from 0 to 50, and the y-axis represents 'E[Wa,1(n)]' ranging from -4 to 8. The chart displays two data series: an empirical series represented by a solid orange line with circular markers, and a theoretical series represented by a dashed orange line. ### Components/Axes * **Title:** Comparison: Symbolic Drift vs. Logarithmic Approximation * **X-axis:** * Label: a (odd) * Scale: 0 to 50, with tick marks at intervals of 10 (0, 10, 20, 30, 40, 50) * **Y-axis:** * Label: E[Wa,1(n)] * Scale: -4 to 8, with tick marks at intervals of 2 (-4, -2, 0, 2, 4, 6, 8) * **Legend:** Located in the top-left corner. * Empirical: Solid orange line with circular markers. * 2 * log₂(a/2) - 2 (theoretical): Dashed orange line. * A horizontal dashed grey line is present at y=0. ### Detailed Analysis * **Empirical Data (Solid Orange Line with Circular Markers):** * Trend: The empirical data generally increases with fluctuations. It starts at approximately -2 at a=1, rises sharply to around 2 at a=5, then continues to increase with oscillations, reaching approximately 8.5 at a=50. * Data Points: * a=1: E[Wa,1(n)] ≈ -2 * a=5: E[Wa,1(n)] ≈ 2 * a=10: E[Wa,1(n)] ≈ 4 * a=15: E[Wa,1(n)] ≈ 4.5 * a=20: E[Wa,1(n)] ≈ 6 * a=25: E[Wa,1(n)] ≈ 5.7 * a=30: E[Wa,1(n)] ≈ 7 * a=35: E[Wa,1(n)] ≈ 6.5 * a=40: E[Wa,1(n)] ≈ 7.7 * a=45: E[Wa,1(n)] ≈ 7.5 * a=50: E[Wa,1(n)] ≈ 8.5 * **Theoretical Data (Dashed Orange Line):** * Trend: The theoretical data increases logarithmically. It starts at approximately -4 at a=1, rises to around 3 at a=10, and continues to increase, reaching approximately 7.5 at a=50. * Data Points (Approximate): * a=1: 2 * log₂(1/2) - 2 = -4 * a=10: 2 * log₂(5) - 2 ≈ 2.6 * a=20: 2 * log₂(10) - 2 ≈ 4.6 * a=30: 2 * log₂(15) - 2 ≈ 5.9 * a=40: 2 * log₂(20) - 2 ≈ 6.6 * a=50: 2 * log₂(25) - 2 ≈ 7.3 ### Key Observations * The empirical data fluctuates around the theoretical logarithmic approximation. * The theoretical approximation underestimates the empirical data, especially at lower values of 'a'. * The empirical data exhibits oscillations, suggesting variability not captured by the theoretical model. ### Interpretation The chart compares the empirical symbolic drift with a theoretical logarithmic approximation. The empirical data shows a general increasing trend, but with significant oscillations. The theoretical approximation provides a smoothed, logarithmic representation of this trend. The discrepancy between the two suggests that the theoretical model captures the overall trend but fails to account for the variability present in the empirical data. This could be due to factors not included in the theoretical model, such as specific properties of the symbolic sequences being analyzed. The oscillations in the empirical data might represent periodic behaviors or dependencies that are not captured by the logarithmic approximation. </details> Figure 5: Empirical symbolic drift $\mathbb{E}[w_{a,1}(n)]$ for odd $a≤ 50$ , compared to the theoretical curve $2\log_{2}(a/2)-2$ . Minimum occurs at $a=3$ . **Remark B.4 (Logarithmic Structure)** *The shape of $\mathbb{E}[w_{a,1}(n)]$ closely follows a logarithmic law: $$ \mathbb{E}[w_{a,1}(n)]\approx 2\cdot\log_{2}\left(\frac{a}{2}\right)-2 $$ This arises because both $\mathbb{E}[\mathrm{to}(n)]≈ 2$ and $\mathbb{E}[\mathrm{tz}(n^{\prime})]≈ 2$ are nearly constant.* **Remark B.5 (Symbolic Stability Principle)** *Among all affine systems $T_{a,1}(n)=\frac{an+1}{2^{k}}$ , only the classical Collatz case $a=3$ yields: $$ \mathbb{E}[w_{3,1}(n)]\approx-0.83008<0 $$ This makes it the unique globally contracting system in the symbolic framework.* B.6 Symbolic Evaluation for $n=32$ (Even Case) We illustrate the symbolic digitwise emulation for the even input $n=32$ , where $T(32)=16$ . The decimal expansion is: $$ n=2\cdot 10^{0}+3\cdot 10^{1}\quad\Rightarrow\quad r_{0}=2,\quad r_{1}=3 $$ We now compute the updated digits from right to left: | | $\displaystyle p_{0}$ | $\displaystyle=r_{1}\bmod 2=3\bmod 2=1$ | | | --- | --- | --- | --- | We obtain the updated digit sequence $(r_{0}^{\prime},r_{1}^{\prime})=(6,1)$ , which corresponds to: $$ T(32)=6\cdot 10^{0}+1\cdot 10^{1}=16 \tag{32} $$ **Remark B.6** *This confirms that the symbolic transition faithfully emulates the even-case arithmetic of the Collatz map at the digit level, including parity-aware carry handling.* Appendix C Symbolic State Evolution Example The following table illustrates the symbolic digit evolution of a Collatz trajectory starting from $n=13$ . Each row corresponds to a timestep, showing the decimal value, and the symbolic states of the least and next-most significant digits. Table 4: Symbolic FSM states during the Collatz trajectory of $n=13$ | 0 1 2 | 13 40 20 | (1,0,1) (4,0,0) (2,0,0) | (3,1,0) (0,0,0) (0,0,0) | | --- | --- | --- | --- | | 3 | 10 | (1,0,0) | (0,1,0) | | 4 | 5 | (0,0,0) | (5,0,0) | | 5 | 16 | (1,0,0) | (6,1,0) | | 6 | 8 | (0,0,0) | (8,0,0) | | 7 | 4 | (0,0,0) | (4,0,0) | | 8 | 2 | (0,0,0) | (2,0,0) | | 9 | 1 | (0,0,0) | (1,0,0) | **Remark C.1** *The symbolic configuration collapses progressively: from step 2 onward, all states in $s_{1}$ evolve toward the null state $(0,0,0)$ , while $s_{0}$ ultimately enters the terminal cycle described in Theorem 4.9.* Appendix D Full Transition Table of the Symbolic FSM Table 5 lists all possible state transitions for the symbolic digit automaton. Each state is of the form $(r,p,c)$ and maps deterministically to its next state under either division or multiplication by $3n+1$ . The FSM is complete over the symbolic space $\mathcal{S}=\{0,...,9\}×\{0,1\}×\{0,1,2\}$ . State Div target 1 Div target 2 Mul3 target 1 Mul3 target 2 Mul3 target 3 0,0,0 0,0,0 0,1,0 0,0,0 1,0,0 2,0,0 0,0,1 - - 1,0,0 - - 0,0,2 - - 2,0,0 - - 0,1,0 5,0,0 5,1,0 0,1,0 1,1,0 2,1,0 0,1,1 - - 1,1,0 - - 0,1,2 - - 2,1,0 - - 1,0,0 0,0,0 0,1,0 3,0,0 4,0,0 5,0,0 1,0,1 0,0,0 0,1,0 4,0,0 - - 1,0,2 - - 5,0,0 - - 1,1,0 5,0,0 5,1,0 3,1,0 4,1,0 5,1,0 1,1,1 5,0,0 5,1,0 4,1,0 - - 1,1,2 - - 5,1,0 - - 2,0,0 1,0,0 1,1,0 6,0,0 7,0,0 8,0,0 2,0,1 - - 7,0,0 - - 2,0,2 - - 8,0,0 - - 2,1,0 6,0,0 6,1,0 6,1,0 7,1,0 8,1,0 2,1,1 - - 7,1,0 - - 2,1,2 - - 8,1,0 - - 3,0,0 1,0,0 1,1,0 0,1,0 1,1,0 9,0,0 3,0,1 1,0,0 1,1,0 0,1,0 - - 3,0,2 - - 1,1,0 - - 3,1,0 6,0,0 6,1,0 0,0,0 1,0,0 9,1,0 3,1,1 6,0,0 6,1,0 0,0,0 - - 3,1,2 - - 1,0,0 - - 4,0,0 2,0,0 2,1,0 2,1,0 3,1,0 4,1,0 4,0,1 - - 3,1,0 - - 4,0,2 - - 4,1,0 - - 4,1,0 7,0,0 7,1,0 2,0,0 3,0,0 4,0,0 4,1,1 - - 3,0,0 - - 4,1,2 - - 4,0,0 - - 5,0,0 2,0,0 2,1,0 5,1,0 6,1,0 7,1,0 5,0,1 2,0,0 2,1,0 6,1,0 - - 5,0,2 - - 7,1,0 - - 5,1,0 7,0,0 7,1,0 5,0,0 6,0,0 7,0,0 5,1,1 7,0,0 7,1,0 6,0,0 - - 5,1,2 - - 7,0,0 - - 6,0,0 3,0,0 3,1,0 0,0,0 8,1,0 9,1,0 6,0,1 - - 9,1,0 - - 6,0,2 - - 0,0,0 - - 6,1,0 8,0,0 8,1,0 0,1,0 8,0,0 9,0,0 6,1,1 - - 9,0,0 - - 6,1,2 - - 0,1,0 - - 7,0,0 3,0,0 3,1,0 1,0,0 2,0,0 3,0,0 7,0,1 3,0,0 3,1,0 2,0,0 - - 7,0,2 - - 3,0,0 - - 7,1,0 8,0,0 8,1,0 1,1,0 2,1,0 3,1,0 7,1,1 8,0,0 8,1,0 2,1,0 - - 7,1,2 - - 3,1,0 - - 8,0,0 4,0,0 4,1,0 4,0,0 5,0,0 6,0,0 8,0,1 - - 5,0,0 - - 8,0,2 - - 6,0,0 - - 8,1,0 9,0,0 9,1,0 4,1,0 5,1,0 6,1,0 8,1,1 - - 5,1,0 - - 8,1,2 - - 6,1,0 - - 9,0,0 4,0,0 4,1,0 7,0,0 8,0,0 9,0,0 9,0,1 4,0,0 4,1,0 8,0,0 - - 9,0,2 - - 9,0,0 - - 9,1,0 9,0,0 9,1,0 7,1,0 8,1,0 9,1,0 9,1,1 9,0,0 9,1,0 8,1,0 - - 9,1,2 - - 9,1,0 - - Table 5: All valid state transitions in the symbolic FSM for all $60$ states $(r,p,c)∈\mathcal{S}$ . Appendix E Symbolic FSM Variants E.1 Quotient-Based FSM (Mod 2) The Mod-2 FSM encodes how the transformation $3n+1$ modifies the binary decay of $n$ . Instead of computing values, it interprets Collatz dynamics structurally via symbolic rules over quotient sequences $q_{i}$ and $b_{i}$ . Let $q=(q_{i})$ be the successive divisions of $n$ by 2, and $b=(b_{i})$ the quotient chain of $3n+1$ . For each index $i$ , the FSM assigns a symbolic label from: $$ \boxed{3n},\quad\boxed{3n+1},\quad\boxed{3n+2} $$ using only local parity and division behavior. The rules are: - Rule 1 (Initial step): If $i=0$ , assign $\boxed{3n+1}$ . - Rule 2 (Parity mismatch): If $\mathrm{par}(q_{i})≠\mathrm{par}(b_{i})$ , then $\boxed{3n+1}$ . - Rule 3 (Clean division, parity match): If $q_{i}//2=q_{i+1}$ : $$ \begin{cases}b_{i}=3q_{i}&\Rightarrow\boxed{3n}\\ b_{i}=3q_{i}+2&\Rightarrow\boxed{3n+2}\end{cases} $$ - Rule 4 (Dirty division): If $q_{i}//2≠ q_{i+1}$ , assign $\boxed{3n+2}$ . - Rule 5 (Tail values): For $b_{i}∈\{2,1\}$ , use explicit matching. This decoder assigns symbolic meanings to how $3n+1$ transforms the structure of $n$ , without arithmetic simulation. E.1.1 Example: $n=31$ | | $\displaystyle q$ | $\displaystyle=[31,\ 15,\ 7,\ 3,\ 1]$ | | | --- | --- | --- | --- | | 0 | 31 | 94 | 1, 0 | – | $3n+1$ | | --- | --- | --- | --- | --- | --- | | 1 | 15 | 47 | 1, 1 | ✗ | $3n+2$ | | 2 | 7 | 23 | 1, 1 | ✗ | $3n+2$ | | 3 | 3 | 11 | 1, 1 | ✗ | $3n+2$ | | 4 | 1 | 5 | 1, 1 | ✗ | $3n+2$ | | 5 | 0 | 2 | 0, 0 | – | induced | | 6 | 0 | 1 | 0, 1 | – | induced | Symbolic sequence: $\boxed{+1,\ +2,\ +2,\ +2,\ +2}$ The trailing entries $b_{5}=2$ and $b_{6}=1$ are not mapped from $q_{i}$ , but are induced by the binary expansion of $3n+1$ . E.1.2 Structural Use This symbolic decoder enables: - Structural classification of integers via FSM-derived symbol sequences - Prediction of expansion/contraction via drift: $$ w(n)=\mathrm{to}(n)\cdot\log_{2}\left(\frac{3}{2}\right)-\mathrm{tz}(n^{\prime}) \tag{32} $$ - Recognition of special forms (e.g., $2^{k}-1$ ) with high symbolic lifespan - Logical, rather than arithmetic, interpretation of the $3n+1$ process Together with the digit-level FSM, the Mod-2 FSM provides a layered structural view of Collatz dynamics. E.2 Local Bit-Level FSM The bit-level FSM eliminates the need to compute $3n+1$ . It operates directly on the binary form of $n$ , using local rules and a sliding window. - Input: binary string $b_{k-1}... b_{0}$ of odd $n$ - Step: For each window $(b_{i+1},b_{i})$ : | | $\displaystyle 0$ | $\displaystyle\mapsto 0$ | | | --- | --- | --- | --- | - Growth prediction: $$ \Delta\mathrm{bits}(3n+1)=\begin{cases}+2&\text{if }3n+1\geq 2^{k+1}\\ +1&\text{otherwise}\end{cases} $$ - Symbol label: $$ \texttt{10}\Rightarrow\boxed{+2},\quad\texttt{1}\Rightarrow\boxed{+1} $$ - Result: FSM yields symbolic string over $\{+2,+1,/2,...\}$ , purely from $n$ ’s bits E.2.1 Example: $n=161=\texttt{10100001}_{2}$ - $3n+1=484=\texttt{111100100}_{2}$ , bit length grows from $8$ to $9$ - Symbol assigned: $\boxed{+1}$ - Followed by 3 halving steps: $\boxed{/2,\ /2,\ /2}$ Implication Each symbolic growth (e.g. $+2$ ) structurally creates trailing zeros → these must be consumed via division. Thus: $$ \exists\ k\ \text{with }w(T^{k}(n))<0\Rightarrow\text{Convergence} $$ E.2.2 Symbolic Length as Structural Predictor The bit-level FSM not only encodes symbolic structure, but also permits a deterministic symbolic determination of the exact number of steps until convergence. While not a closed-form formula, the symbolic step count $$ L(n):=|\sigma(n)| $$ can be computed by applying only local bit-level rules—without evaluating $3n+1$ or simulating classical values. At each stage, the number of trailing ones $\mathrm{to}(n)$ determines a symbolic growth phase, followed by trailing zeros $\mathrm{tz}(n^{\prime})$ that encode a decay phase. Repeating this symbolic process yields: $$ L(n)=\sum_{k=0}^{m}\left(\mathrm{to}(n_{k})+\mathrm{tz}(n_{k}^{\prime})\right), $$ where $n_{k+1}$ is the result of structurally applying $\mathrm{to}(n_{k})$ T3-steps and $\mathrm{tz}(n_{k}^{\prime})$ halving steps. Theorem. For any odd $n$ , the total symbolic step count $L(n)$ equals the number of symbolic FSM transitions from $n$ to $1$ , and can be computed without evaluating $3n+1$ . This construction replaces arithmetic simulation with a fully symbolic recursion driven by bit patterns. While not an algebraic shortcut, it is a structurally grounded and mechanizable prediction mechanism. E.3 Comparison Both FSMs symbolically encode the $3n+1$ dynamics. - The Quotient FSM reconstructs the $3n+1$ action by comparing division chains $q_{i}$ and $b_{i}$ - The Bit FSM predicts symbolic drift directly from the binary representation of $n$ Both yield the same drift function $w(n)$ and confirm symbolic convergence. The bit-level FSM, however, requires no access to $3n+1$ , making it truly predictive, symbolic, and deterministic.