Generalized Collatz is undecidable (Conway)

Parent: collatz

Conway (1972, Unpredictable Iterations) generalized the [[collatz|3n+1]] map and proved the family is Turing-complete — so its convergence question has no decision procedure.

Generalized Collatz function

Fix a modulus d and rationals $a_0,b_0,\dots,a_{d-1},b_{d-1}$. Define g(n) = aᵢ·n + bᵢ whenever n ≡ i (mod d), with the aᵢ,bᵢ chosen so g(n) is always a positive integer. (Collatz is d=2: g(n)=n/2 or 3n+1.)

Conway (1972)

The problem — given such a g and a start n, does the orbit n, g(n), g²(n), … ever reach 1? — is undecidable.

Proof

Reduce the halting problem. A register (Minsky) machine is Turing-complete; its instructions are inc(j) (increment register j, go to state s') and test/dec(j) (if register j>0, decrement and go to s', else go to s''). Deciding whether it halts is undecidable.

Encode a configuration (current state s, register contents r₁,…,rₘ) as one integer, using distinct primes $p_s$ (one per state) and $q_j$ (one per register):

$$N=p_s\cdot\prod_{j=1}^{m} q_j^{\,r_j}.$$

One application of g = one machine step. Take the modulus $d$ to be the product of all these primes. Then $N \bmod d$ reveals both which state we're in (the unique $p_s$ dividing $N$) and which registers are zero (whether $q_j \mid N$). Case-split on that residue and multiply by the matching rational:

• inc(j) → s': multiply by $a = p_{s'}\,q_j / p_s$;
• test/dec(j): if $q_j \mid N$, multiply by $p_{s'} / (p_s q_j)$; else by $p_{s''} / p_s$.

Each rule is "multiply N by a constant fixed by N's residue class mod d", i.e. exactly a generalized-Collatz step (and each is integer-valued by construction). Send the halt state's configuration to 1.

Now the machine halts ⟺ the g-orbit of the start configuration reaches 1. A decider for "reaches 1" would decide halting — contradiction. ∎

FRACTRAN (Conway, 1987) is the same idea as a language: a program is a list of fractions f₁,…,fₖ; from n, replace it by n·fᵢ for the first i making the product an integer; halt if none does. It is Turing-complete (Conway's PRIMEGAME even enumerates the primes) — generalized-Collatz undecidability is the corollary.

Tie to the thread

This is the concrete face of "does the iteration converge?" = halting = undecidable in general (recursion-is-a-phase-transition). You only recover a decidable answer by restricting — a contraction or a well-founded P×C measure is a decidable sufficient certificate (recursion-convergence-contraction, relaxing-undecidability). Collatz is hard precisely because it offers no such measure.