概率化——测度、几率与极限
用一个测度或一个概率为一的命题,替换掉一个确定的是/否判断。
Chaitin 的 Ω——停机的测度
停机概率对于一台无前缀通用机器
U,,求和取遍所有会停机的程序p——即一个随机程序停机的概率。
Ω 是算法随机的(它的每一位都不可压缩)且不可计算,但却是左半可计算(left-c.e.)的:可以从下方逼近计算(跑更多程序,Ω 只会上升)。于是"停机"这件事有了一个可逼近的数值"量",即便没有哪一位是可判定的。它的每一位都是不可化简的数学事实。
几乎必然收敛
在随机动力学中,"收敛"被替换为"以概率一收敛"(随机逼近,Robbins–Monro;鞅收敛)。那些不收敛的例外路径构成一个测度为零的集合——对动力学而言是不可见的。
极限中可计算(Gold,1965)
极限递归 / 试错法: 输出一个猜测,并允许有限次地改动它;最终的猜测是正确的。(全)停机谓词正是以这种方式可计算的——它属于 Δ₂。你永远不知道自己已经做完了,但你在极限意义上是对的。
联系: "通常会收敛"的自我演化 agent 正落在这里——是几乎必然收敛/极限收敛,而非可判定的收敛;剩下的这份不确定性,正是为什么仍需要一个certificate或tolerance才能真正落定的原因。