2026-08-28·by Sijie Wang#math#logic#relaxation

probabilistic-undecidability

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

上级:relaxing-undecidability

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

Chaitin 的 Ω——停机的测度

停机概率

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

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

几乎必然收敛

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

极限中可计算(Gold,1965)

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

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

about this entry

One of sijie's wiki entries. The AI on this site is grounded in the same corpus and answers in sijie's voice, with citations back to entries like this one — answering costs sijie money, so it waits behind a code: enter an access code →

probabilistic-undecidability