可计算测度下的随机性

同一个有限串在不同模型下可以很普通，也可以极其罕见。随机性首先是“相对于指定可计算概率源没有有效可识别的零测异常”，不是“每个比特都有一半机会为一”。

更换测度应同时更换检验预算和信息基准。若真实硬币偏向正面，却仍以公平币模型检查长期频率，检验发现的是源模型不匹配。

偏置币的预算要重新算 ​

对可计算 $p\in (0,1)$，独立 Bernoulli$(p)$ 源满足

取 $p=1/3$，柱集 [101] 的质量为 $(1/3{)}^2(2/3)=2/27$，不是公平币的 $1/8$。令 $U_n=[0^{2n}]$，则

因此 $(U_n)$ 是一个统一有效的检验，全零序列被捕获。若误用 $[0^n]$，其质量 $(2/3{)}^n$ 大于 $2^{-n}$，原预算不成立；增加前缀长度才修复检验。

可计算序列也可能对某个测度随机 ​

若 $\mu ={\delta }_{0^{\mathrm{\infty }}}$，则全零序列是可计算的，却是 $\mu$-随机。任何包含它的集合测度都为一，不可能属于预算小于一的检验层。更一般地，任意正质量原子 $X$ 都是其测度下的随机点：取 $2^{-n}<\mu (\{X\})$ 即知 $X\notin U_n$。

所以“随机序列必不可计算”依赖公平币或适当无原子条件，不能照搬到所有可计算测度。对于 $\mu ([\sigma ])=0$ 的柱集，则恒取 $U_n=[\sigma ]$ 就能排除其中全部序列。

压缩基准变成自信息 ​

对可计算概率测度，广义 Levin–Schnorr 刻画以前缀复杂度公理库前缀复杂度与 Levin–Schnorr 定理Prefix-free Kolmogorov complexity · Levin–Schnorr theorem · Kraft–Chaitin theorem · 前缀 Kolmogorov 复杂度构造通用前缀机与 Kraft–Chaitin 在线编码，证明无限序列的 Martin-Löf 随机性等价于所有前缀的压缩亏损有统一常数界。给出

零概率前缀使右边为无穷，因此不可能满足；正质量原子的前缀自信息有界，与上例相容。偏置币典型频率下，每位自信息趋于二元熵 $h(p)$，不必趋于一。比较不同源的复杂度时，先校准这条基准。

这里还可讨论无限序列之间的可计算映射 $F:2^{\mathbb{N}}\to 2^{\mathbb{N}}$：一台oracle 机器公理库预言机图灵机Oracle Turing machine可在一步内查询某固定语言成员资格的相对可计算性模型。以输入序列为查询源，对每个序列及每个所求输出位都在有限步后给出答案。这不是把无限序列当作一次读完的有限字；每次有限输出仅查询有限多个输入位。

若这种全定义映射把可计算测度 $\mu$ 推到可计算测度 $\nu$，则它把 $\mu$-随机点送到 $\nu$-随机点。对目标柱集，枚举所有已经产生相应输出前缀的有限查询轨迹，再把有限个指定坐标的答案补成有限前缀柱集，便能有效枚举其原像。因此把 $\nu$-检验各层取原像，就得到同预算的 $\mu$-检验。对仅几乎处处定义的映射，必须额外检查有效定义域及随机点是否位于其中，不能跳过这项条件。

典型集公理库弱典型集Typical set · Weak typical set · Weakly typical set单位自信息接近熵、总概率趋近一的弱典型序列集合。通常控制有限块的频率或自信息，随机性则要求逃过所有有效零测异常。源模型相同是比较二者的前提，通过某一有限样本频率检验不等于认证无限序列随机。