返回学习路线

U14 单元验收：预算、资本和不可知的剩余质量 ​

任务 ​

在独立 Bernoulli$(1/3)$ 源上完成以下工作：构造捕获全零序列的有效检验并核算 Schnorr 条件；写出该源下的公平赌徒等式，计算沿全零路径的资本；比较普通 Martin-Löf、可计算随机与 Schnorr 随机的量词；以阈值请求解释编码定理；最后证明通用前缀机停机概率可从下逼近，并说明真正前 $n$ 位和模拟所得前 $n$ 位的区别。

完整解答 ​

1. 预算来自指定测度 ​

令 $U_n=[0^{2n}]$。其测度为 $(2/3{)}^{2n}=(4/9{)}^n\le 2^{-n}$。一台程序输入 $n$ 就能输出对应前缀，所以检验统一有效；测度又是统一可精确计算的有理数，因此它也是该测度下的 Schnorr 检验。全零序列属于全部层。若改用 $[0^n]$，测度 $(2/3{)}^n$ 超预算，原论证失败。

2. 赌徒公平性也要换权重 ​

正确等式是

$$d(\sigma )=\frac{2}{3}d(\sigma 0)+\frac{1}{3}d(\sigma 1).$$

每次把全部资本押在零上，取 $d(\sigma 0)=\frac{3}{2}d(\sigma )$、$d(\sigma 1)=0$，初始资本一。沿 $0^n$ 资本为 $(3/2{)}^n$，无界；遇到一则归零。若仍用公平币的翻倍规则，两边平均值变成 $(4/3)d(\sigma )$，策略凭空产生期望资本，不符合当前源模型。

3. 量词控制检验者的能力 ​

Martin-Löf 失败是：存在一个统一有效开检验，使序列落入所有层；层测度只需满足预算。Schnorr 失败还要求存在统一程序，能以指定误差计算每层最终测度。要求更强的是检验，所以随机序列类反而更大。

可计算随机失败是：存在一个全可计算非负公平赌徒，沿该序列资本无界，即对每个资本阈值都存在某个前缀超过它。定义不提供达到阈值的可计算时刻上界。Schnorr 的赌徒刻画要求另存在可计算、非减、无界的 $h:\mathbb{N}\to {\mathbb{N}}_{>0}$，使 $\underset{n}{lim sup}d(X\upharpoonright n)/h(n)>1$；不能用一般无界成功替代。

在公平币的标准约定下，三类严格关系是 $\mathrm{MLR}⊊\mathrm{CR}⊊\mathrm{SR}$。这个层级结论来自分离定理与构造，不是仅凭一个具体序列的短样本推得。

4. 将累计质量换成码长 ​

设 $m$ 为通用离散下半可计算半测度。首次确认 $m_s(x)>2^{-k}$ 时，为 $x$ 请求长度 $k+2$ 的程序。固定 $x$ 的全部请求权重小于 $m(x)/2$，所以总请求权重不超过 $1/2$；Kraft–Chaitin 定理可统一分配。

取 $k=\lfloor -{\log }_{2}m(x)\rfloor +1$，便有 $K(x)\le -{\log }_{2}m(x)+O(1)$。反向，最短停机程序本身贡献 $2^{-K(x)}$，所以 $m_U(x)\ge 2^{-K(x)}$。通用半测度之间互相常数支配后得到编码定理。

阈值必须严格，避免等待下逼近达到一个只在极限才出现的数。这里只需确认下界，完全没有计算 $m(x)$ 的精确值。

5. Omega 的近似与证书 ​

枚举通用前缀机已经停机的程序，累加 $2^{-|p|}$，得 ${\mathrm{\Omega }}_s\nearrow \mathrm{\Omega }$。Kraft 不等式给总预算一，因此这是合法单调下逼近。

若获知真正前 $n$ 位，设 $q=\lfloor 2^n\mathrm{\Omega }\rfloor 2^{-n}$。等待 ${\mathrm{\Omega }}_s>q$ 后，剩余质量小于 $2^{-n}$，所以任何长度至多 $n$ 的未决程序都不再可能停机。由此可以决定全部短程序的停机情况。

相反，阶段 $s$ 的近似即使显示某个前缀，也没有保证以后不会进位。一份可计算、对所有精度有效的剩余误差界将使停机问题可判定，因此不存在。能不断改善数值，与能宣布当前数位永久正确，是两种不同能力。

验收标准 ​

必须在检验与赌徒两处都使用真实偏置；必须写出统一有效性与无界成功的量词；编码请求须核算总预算并处理严格阈值；Omega 部分须说明为何短程序的一次未来停机会超过剩余预算。只说“不可计算所以不可近似”或“模拟足够久就能确认数位”均不合格。

依据 ​

Downey–Hirschfeldt–Nies–Terwijn《Calibrating Randomness》§§3、10、12；Gács《Lecture Notes on Descriptional Complexity and Randomness》§1.6；本单元各页给出原文链接及源模型边界。