广义 Collatz 不可判定（Conway）

父级：collatz

Conway（1972，Unpredictable Iterations）把 [[collatz|3n+1]] 映射推广为一整个函数族，并证明这个族是图灵完全的——因此它的收敛性问题不存在判定程序。

广义 Collatz 函数

固定一个模 d 以及有理数 $a_0,b_0,\dots,a_{d-1},b_{d-1}$。定义 g(n) = aᵢ·n + bᵢ，只要 n ≡ i (mod d)， 其中 aᵢ,bᵢ 的取值要保证 g(n) 始终是正整数。（Collatz 就是 d=2 的情形：g(n)=n/2 或 3n+1。）

Conway（1972）

这个问题——给定这样一个 g 和起点 n，轨道 n, g(n), g²(n), … 是否会到达 1？——是不可判定的。

Proof

把停机问题归约到这里。寄存器（Minsky）机是图灵完全的；它的指令有 inc(j)（把寄存器 j 加一，转到状态 s'）和 test/dec(j)（若寄存器 j>0，就减一并转到 s'，否则转到 s''）。判定它是否停机是不可判定的。

把一个组态（当前状态 s、寄存器内容 r₁,…,rₘ）编码成一个整数：为每个状态取一个不同的素数 $p_s$，为每个寄存器取一个不同的素数 $q_j$：

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

g 的一次应用 = 机器的一步。 取模 $d$ 为这些素数的乘积。这样 $N \bmod d$ 就同时告诉我们当前在哪个状态（$p_s$ 唯一整除 $N$）以及哪些寄存器为零（$q_j \mid N$ 与否）。按这个余数分情况，乘上对应的有理数：

• inc(j) → s'：乘以 $a = p_{s'}\,q_j / p_s$；
• test/dec(j)：若 $q_j \mid N$，乘以 $p_{s'} / (p_s q_j)$；否则乘以 $p_{s''} / p_s$。

每条规则都是"把 N 乘上一个由 N 模 d 的余数类决定的常数"，也就是恰好一步广义 Collatz 变换（并且按构造，每一步的结果都是整数）。把停机状态对应的组态送到 1。

于是，机器停机 ⟺ 起始组态的 g-轨道到达 1。若存在一个能判定"是否到达 1"的算法，它就能判定停机问题——矛盾。∎

FRACTRAN（Conway，1987）是同一个想法的语言化版本：一个程序是一列分数 f₁,…,fₖ；从 n 出发，在使乘积仍是整数的下标中取第一个 i，把 n 换成 n·fᵢ；若没有这样的 i 就停机。它是图灵完全的（Conway 的 PRIMEGAME 甚至能枚举素数）——广义 Collatz 的不可判定性正是它的一个推论。

与这条脉络的关联

这正是"迭代是否收敛？" = 停机 = 一般情形下不可判定这一命题的具体呈现（recursion-is-a-phase-transition）。要重新得到一个可判定的答案，只能靠加限制——一个压缩映射，或一个良基的 P×C 度量，都是可判定的充分证明（recursion-convergence-contraction、relaxing-undecidability）。Collatz 之所以难，正是因为它不提供这样的度量。