Schnorr 随机性

枚举开集让我们逐渐知道哪些有限观察被列为异常。Schnorr 条件额外要求能控制“还有多少概率质量尚未枚举出来”的误差。这个条件限制检验者，所以通过所有 Schnorr 检验比通过所有 Martin-Löf 检验更容易。

可计算测度不意味着能判定某条序列是否在开集中。质量是整体数量，成员关系是逐点问题；后者仍可能需要无限等待。也不能据有限样本认证某条无限序列 Schnorr 随机。

一个能精确核算预算的频率检验 ​

令 $m_n=16(n+1)$，取

它是有限个长度 $m_n$ 柱集的并，可统一枚举。测度可精确计算为

Hoeffding 不等式公理库Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。给出上界 $2e^{-m_n/8}=2e^{-2(n+1)}\le 2^{-n}$，故它确为 Schnorr 检验。全零序列在每层失败。这里枚举与测度计算都只处理有限个串，不需要猜测一个无限开集最终有多大。

程序的运行时间可以随 $n$ 指数增长，仍不违反定义。Schnorr 随机性中的“可计算”没有规定多项式时间；资源有界随机性是另一个问题。

合法 Martin-Löf 检验未必合法 Schnorr 检验 ​

存在有效开集 $V$，其测度是不可计算的左 c.e. 实数，例如通用前缀机停机程序的柱集并，其测度为 Chaitin 的 $\Omega$公理库Chaitin 停机概率Chaitin Omega · Halting probability把通用前缀机的停机概率写成左 c.e. 随机实数，证明有限真前缀如何决定有限停机问题，并区分近似与误差证书。。在每个枚举串前加 $n$ 个零，得到 $U_n=0^{n}V$，且

这统一有效，满足 Martin-Löf 预算，但连 $\mu (U_0)$ 都不可计算，所以它不是 Schnorr 检验。注意，这只区分检验定义；要证明两个随机性类严格不同，还需构造逃过所有 Schnorr 检验却被某个其他检验捕获的序列。

已知存在严格包含关系

中间的 $\mathrm{CR}$ 是可计算随机性公理库可计算随机性Computable randomness以全可计算非负公平赌徒定义随机性，逐步计算一种押注策略，并说明无界资本和可计算致富速度的差别。。[1, §10] Schnorr 的精确赌徒刻画是：非随机当且仅当存在可计算非负公平赌徒 $d$ 及可计算、非减、无界函数 $h:\mathbb{N}\to {\mathbb{N}}_{>0}$，使 $\underset{n}{lim sup}d(X\upharpoonright n)/h(n)>1$。这里 $h$ 提供可计算的成功速度标尺；仅要求资本无界，则定义的是中间一类。

Schnorr 检验没有像 Martin-Löf 检验那样的通用检验，能以一个合法检验捕获全部非 Schnorr 随机序列。[1, §10.1] 把所有程序列出来并不等于有效识别其中哪些程序的测度误差有统一可计算控制。