Chaitin 停机概率

每个未决程序背后都藏着一小块潜在质量。模拟时间增加会揭开一些质量，却无法知道什么时候已揭完所有重要部分。数值近似可以不断改善；知道“现有前 $n$ 位已经永久正确”则强得多，因为它会排除所有尚未发现、权重至少 $2^{-n}$ 的停机程序。

已知真前缀怎样解决有限停机问题 ​

假设给出 ${\mathrm{\Omega }}_U$ 的真正前 $n$ 位，令 $q=\lfloor 2^n{\mathrm{\Omega }}_U\rfloor 2^{-n}$。因为 ${\mathrm{\Omega }}_U$ 非二进有理数，有

持续枚举直到 ${\mathrm{\Omega }}_s>q$。此时 ${\mathrm{\Omega }}_U-{\mathrm{\Omega }}_s<2^{-n}$，因此不可能再有一个长度至多 $n$ 的新程序停机：它会贡献至少 $2^{-n}$，超过剩余预算。于是已经停机的那些程序之外，所有长度至多 $n$ 的程序都不停止。

例如若获知前三位为 101，则 $q=5/8$。在已枚举质量超过 $5/8$ 的时刻，剩余质量严格小于 $1/8$；任何尚未停机的三位或更短程序便永远不会停机。此处是假设已知真前缀的条件计算，不是在宣称某台指定通用机的前三位确为 101。

为何不能附带统一误差保证 ​

若 ${\mathrm{\Omega }}_U$ 可计算，就能计算它的真实有限前缀，或直接给出任意精度的上下界，再等待下近似与上界差小于 $2^{-n}$。这将决定任意给定短程序是否停机，违反停机问题公理库停机问题不可判定性Halting problem · Undecidability of halting用总停机判断器的自反转构造证明 HALT 不可判定，并区分识别、有限步数检查与局部终止性证明。的不可判定性。因此左逼近没有可计算的统一停止准则。

观察到许多位长时间不变不构成证书。后来一个长时间运行的短程序停机，可能引起二进加法进位，使很靠前的位改变。

随机性从哪里来 ​

由真前 $n$ 位可列出所有长度至多 $n$ 程序的输出，再有效选择一个没有被这些程序输出的字符串 $z$。因此 $K(z)>n$。另一方面，从描述 ${\mathrm{\Omega }}_U\upharpoonright n$ 的程序可以完成上述选择，所以

从而 $K({\mathrm{\Omega }}_U\upharpoonright n)\ge n-O(1)$。利用Levin–Schnorr 定理公理库前缀复杂度与 Levin–Schnorr 定理Prefix-free Kolmogorov complexity · Levin–Schnorr theorem · Kraft–Chaitin theorem · 前缀 Kolmogorov 复杂度构造通用前缀机与 Kraft–Chaitin 在线编码，证明无限序列的 Martin-Löf 随机性等价于所有前缀的压缩亏损有统一常数界。，得到随机性。这里长度 $n$ 可从输出的前缀长度读出，无需额外支付随 $n$ 增长的描述代价。

前缀自由性只保证概率预算，通用性才带来上述不可计算与随机性。若机器只在程序 0、10 上停机，其停机概率为 $3/4$，显然可计算；任意前缀机的停机概率都随机这一说法是错的。

${\mathrm{\Omega }}_U$ 既随机又从下可枚举逼近，说明算法随机并不排斥具有单边有效近似。它也说明程序模拟得到的越来越精细小数，与带误差保证的数值计算是两种不同承诺。