K-平凡性

对一条可计算序列，告诉程序“输出前 $n$ 位”就足够，描述长度主要花在 $n$ 上。$K$-平凡性要求所有前缀都达到近似这种低信息水平，却不要求存在一台程序能统一生成整条序列。

差别藏在最短程序之间的协调：每个前缀都有短描述，不代表这些描述能由长度 $n$ 有效找出，更不代表它们拼成同一个全可计算生成器。

可计算序列为什么满足精确的界 ​

取 $A(n)=1$ 当且仅当 $n$ 是平方数。固定一个程序，先运行 $n$ 的最短自分隔描述，再检查 $0,\dots ,n-1$ 是否为平方数并输出比特。解释器长度固定，所以

这个证明对任意可计算 $A$ 成立，而不依赖计算各位耗时是否短。它证明的是程序长度界，不是时间复杂度界。

非可计算实例为何可能存在 ​

确实存在非可计算、甚至可枚举的 $K$-平凡集。[1, §6] 构造必须在两个要求间协调：偶尔把一个新数枚举进 $A$，以避开某个候选可计算集合；同时补发受影响前缀的新短描述。

若在位置 $x$ 改变比特，所有长度大于 $x$ 的前缀都要更新。构造用阶段成本

估计更新请求的 Kraft 质量；$K_s(n)$ 是已发现程序给出的当前最短描述长度；尚未发现描述时取 $+\mathrm{\infty }$，并约定其权重为零。把改动推迟到足够大的位置，并控制总支付成本，便能用 Kraft–Chaitin 分配所有必要描述。难点是同时满足非可计算性要求与有限总成本；这是一项优先构造定理，不能只凭“选得稀疏”来代替。[1]

信息密度为零还远远不够 ​

把任意随机序列 $R$ 的第 $k$ 位放在 $A(2^k)$，其余位置置零。长度 $n$ 的前缀只包含约 ${\log }_{2}n$ 个随机位，所以复杂度除以 $n$ 趋零。然而从 $A$ 可恢复整个 $R$。若 $A$ 是 $K$-平凡的，下面的低随机性定理会给出 ${\mathrm{MLR}}^A=\mathrm{MLR}$，于是随机的 $R$ 应仍相对于 $A$ 随机；但 $A$ 可逐位算出 $R$，其前缀柱集正构成捕获 $R$ 的 $A$-检验，矛盾。这使用的是相对随机性公理库相对 Martin–Löf 随机性Relative Martin-Lof randomness · Oracle randomness把 oracle 作为检验者可用的额外信息，定义相对随机性，并展示自身 oracle、可计算 oracle 与信息强弱的区别。，不是仅凭跳跃 low：确实存在 low degree 的 Martin-Löf 随机序列。稀疏安放随机信息并不自动满足 $K(n)+O(1)$ 的严格上界。

一个深刻的等价定理给出三种视角：$A$ 为 $K$-平凡；以 $A$ 为 oracle 不会把任何字符串的前缀复杂度统一降低无界量（$K(x)\le K^A(x)+O(1)$）；$A$ 对 Martin-Löf 随机性低，即 ${\mathrm{MLR}}^A=\mathrm{MLR}$。[1, §§7–8]

相对随机性公理库相对 Martin–Löf 随机性Relative Martin-Lof randomness · Oracle randomness把 oracle 作为检验者可用的额外信息，定义相对随机性，并展示自身 oracle、可计算 oracle 与信息强弱的区别。因此说明这种信息虽然可能不可计算，却不会增加有效随机性检验的排除能力。它比 图灵跳跃低性公理库Low 集Low set · Low degree · 低集满足 A′≡T0′ 的自然数集合；定义适用于一般集合，c.e. 构造是其重要专门情形。更特殊，不能把两种“低”当作同一个定义。

由 $K(n)=O(\log n)$ 可知 $K$-平凡序列的有效 Hausdorff 维数公理库有效 Hausdorff 维数Effective Hausdorff dimension · Constructive dimension以可有效押注的维数刻画前缀信息密度下极限，手算稀释随机序列，并解释维数一仍可能不随机。为零。反方向不成立，上面的稀疏编码就是边界。