有效 Hausdorff 维数

维数问：在无限多个长前缀上，每一位至少需要多少不可压缩信息。下极限让低信息密度的长阶段起决定作用；偶尔出现一大块复杂数据，未必提高这个下极限。

当 $s<1$ 时，赌徒每一轮可分给两个孩子的总资本小于公平赌徒的相应预算，成功更困难。可压缩前缀提供便宜的覆盖，正好补偿这项资本折损。

每个随机位后插入一个零 ​

令 $R$ 为 Martin-Löf 随机，取 $X(2i)=R(i)$、$X(2i+1)=0$。由 $X\upharpoonright 2m$ 可恢复 $R\upharpoonright m$，故

反过来，从 $R$ 的前 $m$ 位可输出这 $2m$ 位，且 $K(R\upharpoonright m)\le m+O(\log m)$，故上界为 $m+O(\log m)$。奇数长度只多一位，因此复杂度比值趋于 $1/2$，得到 ${\dim }_{\mathrm{eff}}(X)=1/2$。

这个例子不是把随机性一分为二：$X$ 具有完全可预测的奇数位，明显不随机；维数记录剩下随机信息所占的渐近密度。

维数一仍可有可计算异常 ​

在位置 $2^k$ 固定放零，其余位置按顺序放入随机序列 $R$。长度 $n$ 中只删去 $O(\log n)$ 个随机位置，提取其余位可得

结合一般上界，信息密度趋一。但要求前 $m$ 个指定位置都为零的事件测度恰为 $2^{-m}$，构成有效检验，所以 $X$ 不随机。Martin-Löf 随机性要求复杂度亏损有统一常数界，维数一只要求亏损相对 $n$ 可以忽略。

刻画定理的编码机制 ​

先设 $t<r$ 是非负有理数，且有无限多个前缀 $\sigma =X\upharpoonright n$ 满足 $K(\sigma )<tn$。每个停机程序 $p$ 输出一个有限串 $\sigma$ 后，把质量 $2^{-|p|}$ 放在 $[\sigma ]$ 中，并在其后续坐标上按公平币分配。把所有程序的贡献相加，得到总质量至多一、柱集质量 $M([\tau ])$ 下半可计算的测度：观察到一次停机，就能计算它对任一柱集的有理贡献。令

柱集分裂等式使它成为下半可计算的 $r$-赌徒。对于上述可压缩前缀，其最短程序至少贡献 $2^{-K(\sigma )}$，故 $d_r(\sigma )>2^{(r-t)n}$，沿这些前缀无界。这给出维数不超过复杂度密度下极限。

反过来，设下半可计算 $s$-超赌徒 $d$ 成功，取有理数 $r>s$。逐层迭代超赌徒不等式，有

对每个 $n\ge 1$，枚举所有已证实 $d(\sigma )>1$ 的长为 $n$ 的串，各请求长度 $\lceil rn\rceil +c$，同一串只请求一次。这些请求的总 Kraft 权重至多

选择一个足够大的固定整数 $c\ge 0$ 使其至多一，Kraft–Chaitin 定理便给出同一台前缀机。成功保证沿 $X$ 有无限多个这样的前缀，所以其复杂度密度下极限至多 $r$。让 $r$ 从上逼近 $s$，再取成功赌徒参数的下确界，便得反向不等式。证明只枚举严格资本下界，没有假定能够有效判定“首次越界”的最短前缀。[1,2]

$K$-平凡公理库K-平凡性K-triviality · K-trivial set用前缀复杂度接近长度本身的描述成本定义 K-平凡集，区分统一常数、可计算性、零维数与低性。序列和所有可计算序列维数均为零，但零维数不等于可计算。用越来越稀疏的位置保存不可计算数据，仍可能保留全部图灵信息而令密度归零。

若将 liminf 换为 limsup，得到的是有效强维数（与有效 packing 维数对应），衡量高信息密度阶段；不能只换一个极限符号而沿用同一个名称。