概率化——测度、几率与极限

上级：relaxing-undecidability

用一个测度或一个概率为一的命题，替换掉一个确定的是/否判断。

Chaitin 的 Ω——停机的测度

停机概率

对于一台无前缀通用机器 U，$\Omega = \sum_p 2^{-|p|}$，求和取遍所有会停机的程序 p——即一个随机程序停机的概率。

Ω 是算法随机的（它的每一位都不可压缩）且不可计算，但却是左半可计算（left-c.e.）的：可以从下方逼近计算（跑更多程序，Ω 只会上升）。于是"停机"这件事有了一个可逼近的数值"量"，即便没有哪一位是可判定的。它的每一位都是不可化简的数学事实。

几乎必然收敛

在随机动力学中，"收敛"被替换为"以概率一收敛"（随机逼近，Robbins–Monro；鞅收敛）。那些不收敛的例外路径构成一个测度为零的集合——对动力学而言是不可见的。

极限中可计算（Gold，1965）

极限递归 / 试错法： 输出一个猜测，并允许有限次地改动它；最终的猜测是正确的。（全）停机谓词正是以这种方式可计算的——它属于 Δ₂。你永远不知道自己已经做完了，但你在极限意义上是对的。

联系： "通常会收敛"的自我演化 agent 正落在这里——是几乎必然收敛/极限收敛，而非可判定的收敛；剩下的这份不确定性，正是为什么仍需要一个certificate或tolerance才能真正落定的原因。