Martin-Löf 随机性

检验逐步收紧“可疑序列”的概率预算。第一层可以很宽，后续层至多占 $1/2,1/4,1/8,\dots$ 的质量。一条序列如果始终躲在同一套有效规则圈出的这些小集合里，就有一个可以用程序描述的零概率异常来解释它。随机序列要求避开所有这种异常。

开集与有限观察的关系很直接：一旦检验列出了 $\sigma$，而已观察到的比特以 $\sigma$ 开头，就有有限证据证明 $X\in U_n$。相反，观察很久仍未遇到这样的前缀，不能证明 $X\notin U_n$；枚举器以后可能再输出一个命中的柱集。因此定义中的“存在一层不属于”是数学条件，并未附带一个总会停机的认证程序。

为什么只排除有效描述的零集？每条指定序列的单点集都满足

若把落入任意零测集都称为不随机，每条序列都会因自身的单点集而被排除。有效性限制了哪些零集能充当统一的反证，使“单条序列随机”成为一个有内容的概念。

同样，不能把统一有效性弱化为“每个 $U_n$ 单独有一个程序”。对任意 $X$，每个固定的有限串 $X\upharpoonright n$ 都可以写死在某个程序里，于是每个 $[X\upharpoonright n]$ 单独都是有效开集；但这些程序未必能由 $n$ 统一生成。若忽略这一点，上面的单点排除会再次把所有序列都排除掉。

可计算序列必然失败 ​

称 $X$ 可计算，是指存在全可计算函数公理库可计算函数Computable function · Recursive function有图灵机对每个合法输入都停机并输出其值的全函数。在输入 $i$ 时输出 $X(i)$。这时令

程序可以按 $n=0,1,2,\dots$ 计算前缀并输出 $(n,X\upharpoonright n)$，所以开集列统一有效；每层质量恰为 $2^{-n}$。由于 $X\in U_n$ 对所有 $n$ 成立，$X$ 不随机。运行时间再长也不改变这个证明，只要每个比特最终都能算出。

例如 $010101\cdots$ 中 1 的长期频率为 $1/2$，却仍被上述前缀检验捕获。满足这一条频率规律不足以通过所有有效检验。

非可计算仍不足以随机 ​

取任意不可计算的比特序列 $Y$，把它放进奇数坐标，并让偶数坐标全部为零：

若 $X$ 可计算，读取奇数位就能计算 $Y$，所以 $X$ 不可计算。然而令

当 $n=0$ 时取整个空间。对 $n>0$，枚举所有长为 $2n$、偶数坐标为零的串，就得到 $U_n$。它由 $2^n$ 个互不相交的柱集组成，每个质量为 $2^{-2n}$，故

枚举过程对 $n$ 统一，而 $X$ 在每一层里，所以仍不随机。不可计算只排除了“程序逐位生成整条序列”，没有排除程序识别出无限多位上的固定结构。

弱典型性与无限序列随机性 ​

弱典型集公理库弱典型集Typical set · Weak typical set · Weakly typical set单位自信息接近熵、总概率趋近一的弱典型序列集合。检验有限串的单位自信息是否接近源的熵。公平币源下，每条长为 $m$ 的串都有概率 $2^{-m}$，单位自信息恒为 $1$，因此每条有限串都弱典型，包括全零串。全零无限序列的每个前缀都弱典型，它本身却被可计算前缀检验捕获。

这里的差别来自定义所检查的对象与条件：弱典型性研究固定概率模型中的有限块及其质量，Martin-Löf 随机性研究单条无限序列能否逃过所有统一有效的零测异常。不能把弱典型性换称为频率典型性，再据此推出二者等价。

随机序列存在，而且占据概率一 ​

对任意合法检验 $(U_n)$，单调性给出

所以 $\mu (N_U)=0$。程序只有可数多个，合法检验也至多可数多个。用可数并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。合并它们的失败集，便得

这个存在性证明不需要判定哪些程序确实给出了合法检验。它只在集合论意义上取合法程序的可数子集，再对零集取并。[3] 结合前面的前缀检验，随机序列必然不可计算。

通用检验：先修整预算，再合并所有程序 ​

更强的结论是，存在一个合法检验 $(T_n)$，其失败集恰好包含所有非随机序列。构造的困难在于：可以列举所有程序，却不能直接把它们都当作合法检验。有些程序会在某一层输出过多柱集，破坏预算。以下构造把每个候选程序都修整成合法检验，并保证原本合法的程序不受影响。[2]

先说明一个有限计算。给定有限串集合 $F$，删除重复串，再删除所有已经有较短前缀留在集合中的串，得到前缀互不包含的集合 $P$。两个柱集要么不交，要么一个包含另一个，因此

右侧是能够精确比较的二进有理数。例如 $F=\{00,000,01\}$ 的并等于 $[00]\cup [01]$，质量为 $1/2$，不是把三个柱集质量相加得到的 $5/8$。前缀比较与有限整数运算足以完成这项计算，无需近似无限开集的最终质量。

将所有枚举二元组 $(k,\sigma )$ 的程序编号为 $e=0,1,\dots$，忽略不合法的输出编码。对每个 $e$ 和每一层 $k$，维护该层已经接受的有限柱集并。候选程序新输出 $(k,\sigma )$ 时，精确计算把 $[\sigma ]$ 加入后的有限并质量：若不超过 $2^{-k}$，就接受并列出它；否则丢弃这次输出。通过交错模拟各个程序，所有这些操作可以由同一台机器完成。

记最终接受的开集为 $V_k^e$。每个有限阶段的质量都不超过 $2^{-k}$，由测度的从下连续性，最终仍有

例如预算为 $1/4$ 的一层先收到 00，可以接受；再收到 000，并没有增加质量，仍可接受；再收到 01，质量会变为 $1/2$，于是丢弃它。检查的始终是柱集的并，而不是输出次数或字符串长度之和。

如果原程序 $e$ 本来枚举的就是合法检验 $(U_k)$，它的任意有限部分都包含在 $U_k$ 中，质量自然不超过预算。因此修整不会丢弃它的任何输出，且 $V_k^e=U_k$。对不合法的程序，则无需判断哪里出了错；逐步预算检查已经保证修整后的每一层合法。

现在定义移位并集

这仍统一有效：交错运行修整枚举器；每次接受 $(e,k,\sigma )$ 且 $k\ge e+1$ 时，就向第 $n=k-e-1$ 层输出 $\sigma$。由并集界，

所以 $(T_n)$ 是合法检验。若 $X$ 失败于某个由程序 $e$ 枚举的合法检验 $(U_k)$，那么对每个 $n$，

故 $X$ 失败于 $(T_n)$。反过来，失败于 $(T_n)$ 本身就说明不随机。因此

这里不仅得到了一个捕获全部非随机序列的检验，还明确给出了每个候选合法检验对应的层号移位 $e+1$。这个支配关系来自上述构造，不能仅凭“失败集相同”就推给任意其他通用检验。

嵌套约定与有限观察的限度 ​

本页不要求 $U_{n+1}\subseteq U_n$。若需要嵌套版本，可令 ${\hat{U}}_n=\bigcap _{i\le n}{U}_i$。有限个有效开集的交仍有效：枚举各层柱集的有限组合，前缀彼此相容时取其中最长的串，不相容时交为空。于是 ${\hat{U}}_n\subseteq U_n$ 保留预算，而且 $\bigcap _n{\hat{U}}_n=\bigcap _n{U}_n$，随机性定义不变。

任何有限前缀都不能认证或否定无限序列的随机性。给定 $\sigma$，把它接上无限个零，得到一个可计算、因而非随机的延续；另一方面，$[\sigma ]$ 的质量为正，而非随机序列总质量为零，所以同一柱集内也存在随机延续。

概率一的结论依赖已指定的公平独立比特模型，不能单凭有限样本就验证现实发生器满足这个模型。随机性也不表示一个样本满足任意人为挑选的概率一性质：对任意指定的随机 $X$，集合 $2^{\mathbb{N}}\setminus \{X\}$ 仍有概率一，却不含 $X$。本页保证的是避开具有上述统一有效检验形式的异常。