“不能直接把定理中的随机性换成 可计算随机性或 Schnorr 随机性,并照搬标准 oracle 定义下的完整等价式;这些概念的对应方向会失败。[1, §12] 证明中的预算统一与测度有效性正…”
形式陈述
在公平币空间
后一条件表示存在一个全可计算函数,输入
序列
直觉
枚举开集让我们逐渐知道哪些有限观察被列为异常。Schnorr 条件额外要求能控制“还有多少概率质量尚未枚举出来”的误差。这个条件限制检验者,所以通过所有 Schnorr 检验比通过所有 Martin-Löf 检验更容易。
可计算测度不意味着能判定某条序列是否在开集中。质量是整体数量,成员关系是逐点问题;后者仍可能需要无限等待。也不能据有限样本认证某条无限序列 Schnorr 随机。
例子与边界
一个能精确核算预算的频率检验
令
它是有限个长度
Hoeffding 不等式给出上界
程序的运行时间可以随
合法 Martin-Löf 检验未必合法 Schnorr 检验
存在有效开集
这统一有效,满足 Martin-Löf 预算,但连
推论与应用
已知存在严格包含关系
中间的
Schnorr 检验没有像 Martin-Löf 检验那样的通用检验,能以一个合法检验捕获全部非 Schnorr 随机序列。[1, §10.1] 把所有程序列出来并不等于有效识别其中哪些程序的测度误差有统一可计算控制。
参考资料
- [1] R. Downey, D. Hirschfeldt, A. Nies and S. Terwijn, Calibrating Randomness, §§10.1–10.2,Definitions 10.1–10.2、Theorem 10.5。
- [2] André Nies, Computability and Randomness, 2009,随机性概念与 Schnorr 随机性部分。