Loop Termination and Generalized Collatz Sequences

Mishel Carelli · 2026

Read Loop Termination and Generalized Collatz Sequences by Mishel Carelli (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-15094.txt.

Introduction

Mishel Carelli connects termination of integer linear-constraint loops to generalized Collatz sequences, integer sequences linear on every residue class modulo a fixed number. Termination asks whether a loop admits any infinite computation, a question still open for such loops in general. Whether such loops end remains open for loops over integers, rationals, and reals. For one-variable loops, Carelli proves ending is decidable in polynomial time, if a long-standing conjecture holds. In reverse, any choice method for one-variable loops would settle given cases of that conjecture.

Catalog record

CREATORMishel Carelli
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69034
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.15094

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Loop Termination and Generalized Collatz Sequences Mishel Carelli Abstract Linear-constraint loops are programs whose transition relation is specified by a system of linear inequalities. The termination problem asks, given a loop, whether it admits an infinite computation. Decidability of termination remains open for linear-constraint loops over integers, rationals, and reals. We focus on loops over integers and show that they are tightly connected to generalized Collatz sequences – integer sequences generated by maps that are linear on each residue class modulo a fixed natural number. We prove that termination of one-variable linear-constraint loops is decidable in polynomial time, provided a long-standing conjecture about generalized Collatz sequences holds. Conversely, we show that any decision procedure for one-variable loops would prove or refute specific instances of this conjecture, which remain open. Moreover, we show that if a one-variable loop has a cyclic trace, then it also has a cyclic trace of length at most two. CISPA Helmholtz Center for Information Security, [email protected]://orcid.org/0009-0000-2181-8205This work was supported by the European Research Council (ERC) Grant HYPER (No. 101055412). {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003790.10002990¡/concept_id¿ ¡concept_desc¿Theory of computation Logic and verification¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ I want to thank Arkadiy Aliev, Bernd Finkbeiner, and Joël Ouaknine for the useful discussions. ccs Theory of computation Logic and verification keywords Program Verification, Loop Termination, Generalized Collatz Sequences, Linear-Constraint Loops † † runningauthor: Mishel Carelli † † copyright: Mishel Carelli † † category: Track B: Automata, Logic, Semantics, and Theory of Programming † † editors: Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis † † event-title: 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) † † event-shorttitle: ICALP 2026 † † event-acronym: ICALP † † year: 2026 † † event-date: July 7–10, 2026 † † event-location: Royal Holloway, University of London, Egham, United Kingdom † † series-volume: 374 † † articleno: 175 1 Introduction Termination analysis is a long-standing topic in theoretical computer science. The Halting Problem – deciding whether a Turing machine halts on a given input – is undecidable, going back to Turing’s original work. Nevertheless, termination can become decidable when restricted to certain classes of programs. In this paper, we analyze the open problem of termination for Single-Path Linear-Constraint Loops (SLC). This problem originates in program analysis and verification, where incomplete but efficient approaches such as ranking functions [ 22 ] and transition invariants [ 21 ] are used as building blocks in verification tools to prove termination and other liveness properties [ 8 ] , [ 21 ] , [ 10 ] and in Horn Clauses solvers [ 5 ] , [ 27 ] . SLCs are loops of the form \textbf{while}\ (C\boldsymbol{x}\leq d)\ \textbf{do}\ A\left(\begin{array}[]{c}\boldsymbol{x}\\ \boldsymbol{x}^{\prime}\end{array}\right)\leq b. (1) Here, \boldsymbol{x} is the vector of values of the program variables in the current step, and \boldsymbol{x}^{\prime} denotes their values in the next step. Moreover, A and C are matrices with rational coefficients, and b and d are rational vectors. Later in the paper, we introduce an equivalent definition with the loop guard omitted. The decision problem is: given such a loop, does there exist an infinite computation with program variables taking values in \mathbb{Z} from some initial state? The question of whether this problem is decidable was posed two decades ago [ 7 ] , and remains open to this day, not only for loops over \mathbb{Z} , but also over \mathbb{Q} and \mathbb{R} . Recently, decidability over \mathbb{R} has been established in the two-variable case [ 9 ] . Decidability of termination varies across loop classes. We now discuss two additional classes of linear loops to illustrate the current landscape. On the positive side, a prominent decidable class of linear loops called affine SLCs, in which the transition is deterministic and has the form \mathbf{while}\ (C\boldsymbol{x}\leq d)\ \mathbf{do}\ \boldsymbol{x}^{\prime}:=A\boldsymbol{x}+b. Termination of affine SLCs has been proved decidable over \mathbb{R} [ 26 ] – via spectral analysis of A – over \mathbb{Q} [ 7 ] , by symbolic reasoning about matrix powers through eigenvalues, and over \mathbb{Z} [ 11 ] , using different tools from geometry of numbers, such as the Khachiyan–Porkolab result on deciding whether a convex semi-algebraic set contains an integer point. On the negative side, another relevant class of linear loops called Multi-Path Linear-Constraint Loops , which allows conditional choice among several linear updates: \mathbf{while}\ (\text{true})\ \mathbf{do}\ \boldsymbol{x}^{\prime}:=\begin{cases}A_{1}\boldsymbol{x}+b_{1}&\text{if }C_{1}\boldsymbol{x}\leq d_{1},\\ \vdots\\ A_{k}\boldsymbol{x}+b_{k}&\text{if }C_{k}\boldsymbol{x}\leq d_{k}.\end{cases} Termination of such multi-path loops is undecidable over \mathbb{R} and \mathbb{Q} [ 6 ] and over \mathbb{Z} [ 3 ] , even for k=2 , via encodings of counter machines. In [ 7 ] , Braverman asked: “How much nondeterminism can be introduced in a linear loop with no initial conditions before termination becomes undecidable?” Motivated by this question and in light of the subsequent results, SLCs occupy an intriguing middle ground between deterministic, decidable affine SLCs and highly expressive, undecidable multi-path loops. Because nondeterminism in SLCs is convex, it does not allow for modeling the unstructured nondeterminism of counter machines, at least not in a straightforward way. In [ 1 ] , the authors show that allowing a single irrational coefficient makes SLC termination undecidable over \mathbb{Z} , and they describe the SLC termination problem as “the most intriguing” among loop-termination problems. For a complete explanation of these results and further references, we refer the reader to the recent survey on linear loop termination [ 2 ] . In this work, we study the SLC termination problem for the case of one variable. While this restriction may seem severe, we show that this problem is deeply non-trivial even for one-variable loops, connecting it with a long-standing number theoretic conjecture about generalized Collatz sequences . The study of Generalized Collatz sequences is a long-standing topic in number theory [ 15 ] , [ 16 ] , [ 17 ] , [ 19 ] , [ 13 ] , [ 18 ] . These integer sequences are generated by generalized Collatz mappings of the form T(x)=\frac{m_{i}x-r_{i}}{d},\ \ \ \ \text{if }x\equiv i\text{ (mod }d) The Uniform Distribution conjecture [ 15 ] asserts that every unbounded generalized Collatz sequence is uniformly distributed modulo d^{\alpha} for every \alpha\in\mathbb{N} . We formulate a weaker statement, the Reachability Conjecture , which posits that every sequence generated by generalized Collatz mappings of a certain type called weak Collatz mappings, reaches a certain residue class modulo d at least once. We prove the Reachability Conjecture for d=2 . Our main result shows that, if the Reachability Conjecture holds, then termination of one-variable SLCs is decidable in polynomial time. For the other direction, we show that any algorithm deciding termination of one-variable SLCs would, given a weak Collatz mapping, determine whether the Reachability Conjecture holds for all sequences generated by that mapping. All cases with modulus d>2 remain open. This suggests that further progress on SLC decidability will require a deeper understanding of generalized Collatz sequences. Let us give the high-level explanation of the results of this paper and its structure. Section 2 introduces the basic definitions and notation. In particular, we define the SLC termination problem and split it into two subproblems: deciding the existence of cycles (finite traces from some state to itself), and deciding the existence of self-avoiding traces (infinite traces that never

Read the complete text