返回学习路线
U14 单元验收:预算、资本和不可知的剩余质量 施工中 · 内容逐步修订
任务
在独立 Bernoulli( 1 / 3 ) 源上完成以下工作:构造捕获全零序列的有效检验并核算 Schnorr 条件;写出该源下的公平赌徒等式,计算沿全零路径的资本;比较普通 Martin-Löf、可计算随机与 Schnorr 随机的量词;以阈值请求解释编码定理;最后证明通用前缀机停机概率可从下逼近,并说明真正前 n 位和模拟所得前 n 位的区别。
完整解答
1. 预算来自指定测度
令 U n = [ 0 2 n ] 。其测度为 ( 2 / 3 ) 2 n = ( 4 / 9 ) n ≤ 2 − n 。一台程序输入 n 就能输出对应前缀,所以检验统一有效;测度又是统一可精确计算的有理数,因此它也是该测度下的 Schnorr 检验。全零序列属于全部层。若改用 [ 0 n ] ,测度 ( 2 / 3 ) n 超预算,原论证失败。
2. 赌徒公平性也要换权重
正确等式是
d ( σ ) = 2 3 d ( σ 0 ) + 1 3 d ( σ 1 ) . 每次把全部资本押在零上,取 d ( σ 0 ) = 3 2 d ( σ ) 、d ( σ 1 ) = 0 ,初始资本一。沿 0 n 资本为 ( 3 / 2 ) n ,无界;遇到一则归零。若仍用公平币的翻倍规则,两边平均值变成 ( 4 / 3 ) d ( σ ) ,策略凭空产生期望资本,不符合当前源模型。
3. 量词控制检验者的能力
Martin-Löf 失败是:存在一个统一有效开检验,使序列落入所有层;层测度只需满足预算。Schnorr 失败还要求存在统一程序,能以指定误差计算每层最终测度。要求更强的是检验,所以随机序列类反而更大。
可计算随机失败是:存在一个全可计算非负公平赌徒,沿该序列资本无界,即对每个资本阈值都存在某个前缀超过它。定义不提供达到阈值的可计算时刻上界。Schnorr 的赌徒刻画要求另存在可计算、非减、无界的 h : N → N > 0 ,使 lim sup n d ( X ↾ n ) / h ( n ) > 1 ;不能用一般无界成功替代。
在公平币的标准约定下,三类严格关系是 MLR ⊊ CR ⊊ SR 。这个层级结论来自分离定理与构造,不是仅凭一个具体序列的短样本推得。
4. 将累计质量换成码长
设 m 为通用离散下半可计算半测度。首次确认 m s ( x ) > 2 − k 时,为 x 请求长度 k + 2 的程序。固定 x 的全部请求权重小于 m ( x ) / 2 ,所以总请求权重不超过 1 / 2 ;Kraft–Chaitin 定理可统一分配。
取 k = ⌊ − log 2 m ( x ) ⌋ + 1 ,便有 K ( x ) ≤ − log 2 m ( x ) + O ( 1 ) 。反向,最短停机程序本身贡献 2 − K ( x ) ,所以 m U ( x ) ≥ 2 − K ( x ) 。通用半测度之间互相常数支配后得到编码定理。
阈值必须严格,避免等待下逼近达到一个只在极限才出现的数。这里只需确认下界,完全没有计算 m ( x ) 的精确值。
5. Omega 的近似与证书
枚举通用前缀机已经停机的程序,累加 2 − | p | ,得 Ω s ↗ Ω 。Kraft 不等式给总预算一,因此这是合法单调下逼近。
若获知真正前 n 位,设 q = ⌊ 2 n Ω ⌋ 2 − n 。等待 Ω s > q 后,剩余质量小于 2 − n ,所以任何长度至多 n 的未决程序都不再可能停机。由此可以决定全部短程序的停机情况。
相反,阶段 s 的近似即使显示某个前缀,也没有保证以后不会进位。一份可计算、对所有精度有效的剩余误差界将使停机问题可判定,因此不存在。能不断改善数值,与能宣布当前数位永久正确,是两种不同能力。
验收标准
必须在检验与赌徒两处都使用真实偏置;必须写出统一有效性与无界成功的量词;编码请求须核算总预算并处理严格阈值;Omega 部分须说明为何短程序的一次未来停机会超过剩余预算。只说“不可计算所以不可近似”或“模拟足够久就能确认数位”均不合格。
依据
Downey–Hirschfeldt–Nies–Terwijn《Calibrating Randomness》§§3–4、10、12;Gács《Lecture Notes on Descriptional Complexity and Randomness》§1.6;本单元各页给出原文链接及源模型边界。