“这是通用离散下半可计算半测度。算法编码定理断言”
形式陈述
本页采用离散半测度约定。对可数、有效编码的输出集合
时称为半测度。它放宽概率分布的总质量等于一,允许某些概率质量没有产生输出。
若存在由同一全可计算函数在输入
若
交错模拟程序,每发现一个新停机输入便加入其权重,给出单调下逼近;前缀自由性经Kraft 不等式保证总质量至多一。
直觉
质量表示随机输入落在某个会停机输出
丢失质量有两种可兼容解释:随机比特没有形成被接受的程序,或形成的计算没有终止。只观察输出分布时,两者都表现为总质量不足一;若应用需要区分原因,模型必须另加状态。
例子与边界
多个程序会把质量汇到同一输出
设一台机器仅在程序 0、10、110 上停机,分别输出
剩余 110,再发现 0,最后发现 10,10 时断言
下半可计算通常不等于可计算
取一个不可计算的左 c.e. 实数
这一论证说明归一化不是无害修饰。若总质量本身不可计算,除以它可能破坏有效性;不能先强行归一化,再声称得到可计算概率分布。
同一个名称还有树版本
有些文献把
称为连续或树半测度。这里
推论与应用
存在一个通用下半可计算离散半测度
这不是逐点取最大值,后者可能超出总预算。算法编码定理进一步证明通用质量的负对数与最短前缀描述长度只差一个常数。
参考资料
- [1] Péter Gács, Lecture Notes on Descriptional Complexity and Randomness,§1.6.2,Theorem 1.6.3(通用半测度);§1.6.4,Theorem 1.6.5(编码定理)。
- [2] Gregory J. Chaitin, A Theory of Program Size Formally Identical to Information Theory, JACM 22, 1975,pp. 329–340。