“$K$ 平凡性要求所有前缀的复杂度至多为长度本身复杂度加统一常数,并等价于对 Martin Löf 随机性低。它确实蕴含本页的跳跃低性,但条件更强;把两种“低”视为同一个定义,会丢掉它对前缀…”
形式陈述
固定通用前缀复杂度
常数
直觉
对一条可计算序列,告诉程序“输出前
差别藏在最短程序之间的协调:每个前缀都有短描述,不代表这些描述能由长度
例子与边界
可计算序列为什么满足精确的界
取
这个证明对任意可计算
非可计算实例为何可能存在
确实存在非可计算、甚至可枚举的
若在位置
估计更新请求的 Kraft 质量;
信息密度为零还远远不够
把任意随机序列
推论与应用
一个深刻的等价定理给出三种视角:
相对随机性因此说明这种信息虽然可能不可计算,却不会增加有效随机性检验的排除能力。它比 图灵跳跃低性更特殊,不能把两种“低”当作同一个定义。
由
参考资料
- [1] R. Downey, D. Hirschfeldt, A. Nies and S. Terwijn, Calibrating Randomness, §6.1,Theorem 6.2(非可计算 c.e. 例);§7,Theorem 7.4、Corollary 7.9(随机性低性与 jump 低性);§8,Theorem 8.1 及其 decanter 证明纲要(
低性)。 - [2] André Nies, Computability and Randomness, 2009,
-triviality 与 cost functions 部分。