“存在有效开集 $V$,其测度是不可计算的左 c.e. 实数,例如通用前缀机停机程序的柱集并,其测度为 Chaitin 的 $\Omega$。在每个枚举串前加 $n$ 个零,得到 $U n=0…”
形式陈述
固定一台通用前缀自由机
可数前缀集合的 Kraft 不等式保证和不超过一。通用性进一步保证
交错模拟所有程序,阶段
直觉
每个未决程序背后都藏着一小块潜在质量。模拟时间增加会揭开一些质量,却无法知道什么时候已揭完所有重要部分。数值近似可以不断改善;知道“现有前
例子与边界
已知真前缀怎样解决有限停机问题
假设给出
持续枚举直到
例如若获知前三位为 101,则 101。
为何不能附带统一误差保证
若
观察到许多位长时间不变不构成证书。后来一个长时间运行的短程序停机,可能引起二进加法进位,使很靠前的位改变。
随机性从哪里来
由真前
从而
推论与应用
前缀自由性只保证概率预算,通用性才带来上述不可计算与随机性。若机器只在程序 0、10 上停机,其停机概率为
参考资料
- [1] Gregory J. Chaitin, A Theory of Program Size Formally Identical to Information Theory, 1975,停机概率与前缀复杂度。
- [2] R. Downey, D. Hirschfeldt, A. Nies and S. Terwijn, Calibrating Randomness, §4,pp. 13–14:
的定义及随后的随机性证明。