💻 computer science

Loop Termination and Generalized Collatz Sequences

This paper establishes a tight connection between the termination of one-variable linear-constraint loops over integers and generalized Collatz sequences, proving that loop termination is decidable in polynomial time contingent on a specific conjecture about these sequences while also demonstrating that any decision procedure for such loops would resolve open cases of the conjecture.

Original authors: Mishel Carelli

Published 2026-05-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mishel Carelli

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are watching a robot walk through a maze. Every time the robot takes a step, it follows a set of strict rules written on the walls. The big question computer scientists ask is: Will this robot ever get stuck in an endless loop, walking forever without stopping?

This paper tackles that question for a specific type of robot and a specific type of maze. Here is the story of what the author, Mishel Carelli, discovered, explained in simple terms.

1. The Robot and the Rules

The "robot" is a computer program with just one number (a single variable) that changes over time. The "rules" are simple math inequalities (like "the next number must be less than twice the current number plus 5").

The author splits the problem of "will it run forever?" into two scenarios:

The Loop: The robot walks in a circle, visiting the exact same spots over and over again.
The One-Way Street: The robot never repeats a spot, but it keeps walking forever, getting further and further away.

2. The Circle Problem (Cycles)

First, the author looked at the "Loop" scenario.

The Discovery: If a robot with just one number gets stuck in a loop, it doesn't need a giant, complex circle to do it. It only needs a tiny circle of one or two steps.
The Analogy: Imagine a child spinning in a circle. You might think they need a huge playground to spin forever. But this paper proves that if they are spinning at all, they are just spinning in a tiny spot, either standing on one foot (1 step) or hopping back and forth between two spots (2 steps).
The Result: Because we know the circle can't be bigger than two steps, we can easily check if the robot is stuck in a loop. This part of the problem is solved.

3. The One-Way Street Problem (Self-Avoiding Traces)

The harder part is the "One-Way Street." This is when the robot walks forever but never steps on the same number twice.

The Connection to a Famous Puzzle: The author realized that for these one-number programs, the robot's path looks exactly like a famous, unsolved math puzzle called the Collatz Conjecture (or the "3x + 1" problem).
- The Collatz Puzzle: Start with any number. If it's even, divide by 2. If it's odd, multiply by 3 and add 1. Repeat. Does every number eventually fall into the loop 4-2-1? No one knows for sure yet.
- The Paper's Twist: The author created a "weaker" version of this puzzle called the Reachability Conjecture. It asks: "If a number keeps growing forever, will it eventually hit a specific type of number (a specific 'residue class')?"
The Big Trade: The paper shows a perfect two-way street between computer science and number theory:
1. If we can prove this "Reachability Conjecture" is true, then we can instantly tell if any one-number program will stop or run forever.
2. Conversely, if we build a computer program that can decide if these loops stop, then that program would also solve the "Reachability Conjecture."

4. The "Map" of the Robot's Path

To figure out if the robot walks forever, the author used geometry.

Imagine the robot's possible moves drawn on a piece of graph paper. This shape is called a polyhedron (a 3D shape made of flat faces, or in this 2D case, a polygon).
The author looked at which way this shape "points."
- If the shape points in a direction where the numbers get bigger and bigger, the robot walks forever.
- If the shape points in a direction where numbers get smaller, the robot eventually stops.
The Catch: There is a tricky corner case. Sometimes the shape points in a way that looks like it could go forever, but it depends on whether the robot hits that specific "special number" mentioned in the Reachability Conjecture.
- If the Conjecture is true, the robot must eventually hit that special number and stop.
- If the Conjecture is false, the robot might sneak past it and walk forever.

5. The Final Verdict

The paper concludes with a conditional "Yes":

If the "Reachability Conjecture" (a math guess about number patterns) is true, then we have a fast, efficient method to decide if these one-number programs will stop.
If we ever find a way to decide if these programs stop, we will have automatically proven (or disproven) that math guess.

Summary

The paper doesn't solve the famous Collatz puzzle itself. Instead, it acts as a translator. It says: "The problem of stopping computer programs with one number is the exact same problem as a specific unsolved math puzzle about number patterns."

If mathematicians solve the number puzzle, computer scientists can instantly fix the program-stopping problem. If computer scientists fix the program problem, mathematicians will have solved the number puzzle. Until one side solves it, the other remains open.

Technical Summary: Loop Termination and Generalized Collatz Sequences

Problem Statement
The paper addresses the decidability of the termination problem for Single-Path Linear-Constraint Loops (SLCs) over the integers ( $\mathbb{Z}$ ). An SLC is defined by a system of linear inequalities relating current state variables $x$ to next state variables $x'$ :
$\text{while } (Cx \le d) \text{ do } \begin{pmatrix} x \\ x' \end{pmatrix} \le b$
While the termination problem is decidable for affine loops (deterministic updates) over $\mathbb{Z}$ , $\mathbb{Q}$ , and $\mathbb{R}$ , and undecidable for multi-path linear loops, the status of SLCs (which allow convex non-determinism) remains open. The specific focus of this work is the one-variable case ( $n=1$ ), a restriction that, despite its apparent simplicity, connects deeply to unresolved number-theoretic conjectures.

Methodology and Approach
The author decomposes the termination problem into two distinct subproblems based on the nature of infinite traces:

Cyclic Traces: Finite sequences $s_1, \dots, s_k, s_1$ that repeat.
Self-Avoiding Traces: Infinite sequences $s_1, s_2, \dots$ where all states are distinct.

The analysis relies heavily on geometric properties of the transition polyhedron $R \subseteq \mathbb{R}^2$ (the set of valid transitions). The paper utilizes the Minkowski-Weyl theorem to decompose $R$ into a convex hull of vertices plus a recession cone. The behavior of the loop is analyzed by examining the direction of this recession cone relative to specific regions in $\mathbb{R}^2$ (e.g., regions where the absolute value of the variable grows).

Key Contributions and Results

1. Cycle Detection in One-Variable Loops
The paper proves a strong structural result for one-variable SLCs regarding cycles:

Theorem: If a one-variable SLC admits a cycle, it admits a cycle of length at most two.
Implication: This reduces the cycle detection problem to checking for cycles of length 1 or 2. Since checking for bounded cycles can be reduced to Integer Linear Programming (ILP), cycle detection for one-variable loops is decidable.
Contrast: This result does not hold for loops with $n \ge 2$ variables, where cycles of arbitrary length can exist without shorter cycles.

2. Connection to Generalized Collatz Sequences
The core contribution is establishing a tight equivalence between the termination of one-variable SLCs and the Reachability Conjecture for generalized Collatz sequences.

Generalized Collatz Mappings: These are maps $T: \mathbb{Z} \to \mathbb{Z}$ defined piecewise based on residue classes modulo $d$ .
Weak Collatz Mappings: A specific subclass where the map takes the form $T(x) = \lfloor \frac{mx - (a+i)}{d} \rfloor$ .
Reachability Conjecture: Posits that for any weak Collatz mapping, if a sequence is unbounded, it must eventually visit a specific residue class modulo $d$ (specifically, where $mT^k(n) \equiv a \pmod d$ ).
Equivalence: The paper proves that any algorithm capable of deciding termination for one-variable SLCs could also decide the Reachability Conjecture for specific weak Collatz mappings. Conversely, if the Reachability Conjecture holds, termination for one-variable SLCs becomes decidable.

3. Main Theorem: Conditional Decidability

Theorem: If the Reachability Conjecture holds, then the termination of one-variable SLCs over integers is decidable in polynomial time.
Mechanism: The decision procedure involves:
1. Checking for cycles of length $\le 2$ (via ILP).
2. Analyzing the recession cone of the transition polyhedron to determine if it points toward regions of unbounded growth.
3. In "thin" cases where the recession cone is a line or a single ray, the analysis reduces to checking the "height" of the polyhedron's integer slices. If the height is small, the trace corresponds to a weak Collatz sequence. The Reachability Conjecture is invoked to conclude that such sequences cannot be self-avoiding (i.e., they must eventually hit a residue class that forces termination or a cycle).

4. Partial Results on the Conjecture

The paper proves the Reachability Conjecture for the case where the modulus $d=2$ .
For $d > 2$ , the conjecture remains open. The paper provides an example (a mapping with $d=3$ ) where the conjecture is currently unresolved, illustrating that progress on SLC termination is currently bottlenecked by number-theoretic limitations.

Significance and Claims
The paper positions the one-variable SLC termination problem as a "middle ground" between fully decidable affine loops and undecidable multi-path loops.

Theoretical Insight: It demonstrates that the difficulty of loop termination is not merely a matter of program complexity but is intrinsically linked to deep number-theoretic properties of integer sequences.
Conditional Result: The paper does not claim to have solved the termination problem unconditionally. Instead, it provides a polynomial-time decision procedure conditional on the Reachability Conjecture.
Semi-algorithm: Without assuming the conjecture, the proposed method acts as a semi-algorithm: it can prove termination or non-termination in most cases but fails to return an answer for specific "thin" traces that correspond to open instances of the Collatz conjecture.

In summary, the work reframes the loop termination problem for a specific class of programs as a number-theoretic problem, proving that resolving the former is equivalent to resolving specific instances of the latter.