科拉茨猜想（3n+1 问题）

父级：number-theory · 动力学视角：orbit → collatz-orbit-statistics

迭代 T(n) = n/2（当 n 为偶数时）或 3n+1（当 n 为奇数时），从任意 n ≥ 1 出发。猜想：每一条轨道最终都会到达 1（此后进入 1→4→2→1 的循环）。此问题自约 1937 年起悬而未决；已对所有 n < 2⁶⁸ 验证成立，但仍无证明。Erdős 曾说："数学还没有为这类问题做好准备。"

基本观察：

• 在 n 为奇数时执行 3n+1 后，结果必为偶数，因此后面总会紧跟一次 /2——人们常常转而研究这一"捷径"映射 n ↦ (3n+1)/2。
• 困难之处在于，看不出有任何明显的递减度量（良基秩）——数值在下降之前可能先攀升得很高（例如从 27 出发会先冲到 9232 的峰值）。没有这样一种度量，就无法套用通常的终止性论证（recursion-convergence-contraction）。

为什么如此困难——一个可计算性角度的解释

3n+1 映射只是某个函数族中的一个具体实例，而这个族作为一个整体是不可判定的：Conway 的广义科拉茨函数可以模拟任意计算，因此"轨道是否到达 1"这一问题不存在通用算法。科拉茨问题正处在这个不可判定的族之中——定义与不可判定性的证明见 generalized-collatz。

提醒。 这个函数族不可判定，并不意味着这一个具体实例在形式上也不可判定——一个固定的实例总有一个确定的（哪怕未知的）真值。这只是解释了问题为何困难，并不是"科拉茨猜想不可证明"的证明。