计算控制与算法充分统计量的研究

### 计算控制与算法充分统计量的研究 #### 1. 迪阿列克托解释中的计算控制 在迪阿列克托解释中，对于相关开放假设的负提取内容，使用标志 `+∀` 时，可能无法节省对 `y` 的昂贵计算。若能通过标记 `±∀` 舍弃 `y` 的所有计算用途，才有可能实现节省。 对于所有弱标志，都能构建类似场景。这表明移除某个计算组件的单一用途可能有助于清理提取的程序，但要提高效率，必须移除其所有用途。从语法角度重新表述，仅使用弱标志（即无法应用相应强标志），只能起到“卫生”作用，且这种情况是迪阿列克托解释所特有的，因为这里存在计算相关性的对偶性。 迪阿列克托解释比可实现性允许更丰富的统一注释集。该方法可扩展到具有有限类型的海廷算术，能在迪阿列克托上下文中完全模拟修改后的可实现性效果，包括伯杰的统一量词。 通过注释 `A⊕` 和 `A⊖`，若注释证明在计算上正确，就能完全移除给定证明中公式的正或负内容。未来研究的一个方向是探讨在哪些情况下这在实际中可行；若不可行，如何以最优方式自动引入额外注释来修复计算正确性。 #### 2. 算法最小充分统计量的定义与问题 ##### 2.1 充分统计量的定义 设 `x` 为二进制字符串，若有限集 `A` 包含 `x`，且 `A` 的柯尔莫哥洛夫复杂度与 `A` 的对数基数之和接近 `x` 的柯尔莫哥洛夫复杂度 `C(x)`，即 `C(A) + log₂ |A| ≈ C(x)`，则称 `A` 为 `x` 的（算法）充分统计量。 这意味着 `x` 的两部分描述 `(A∗, i)`（其中 `A∗` 是 `A` 的最小长度描述，`i` 是 `x` 在 `A` 中按字典序排列的索引）与 `x` 的最小长度编码一样简洁。实际上，`A` 是 `x` 的充分统计量当且仅当 `C(A|x) ≈ 0` 且 `C(x|A) ≈ log |A|`。前者表明 `A∗` 中的信息是 `x` 中信息的一部分，后者表明 `x` 是 `A` 的典型成员，没有能让我们在给定 `A` 时以更短方式描述 `x` 的规律。 为使充分统计量的概念更严格，需明确“接近”的含义。一种定义是固定常数 `c`，若 `|(C(A) + log |A|) - C(x)| ≤ c`，则称 `A` 为充分统计量。更精确地，有些研究使用前缀复杂度 `K` 代替普通复杂度 `C`。若选择足够大的 `c`，充分统计量是存在的，例如 `A = {x}`。 为避免讨论 `c` 应多小，我们称满足上述不等式的 `A ∋ x` 为 `c` - 充分统计量，`c` 越小，`A` 越充分。由于不等式 `C(x) ≤ C(A) + log |A|` 仅在对数精度下成立，所以该概念仅在 `c = O(log n)` 时才有意义。 ##### 2.2 最小充分统计量的问题 自然地，我们希望从给定字符串 `x` 中尽可能多地挤出噪声。每个充分统计量 `A` 能识别 `x` 中 `log |A|` 位的噪声，因此具有最大 `log |A|`（即最小 `C(A)`）的充分统计量能识别 `x` 中最大可能的噪声量，这样的充分统计量称为最小充分统计量（MSS）。 然而，这个概念并非对所有字符串都定义良好。对于某些字符串 `x`，无论 `c` 取何值，都难以直观地确定 MSS。存在这样的字符串，当 `c` 稍有增加时，最小 `c` - 充分统计量的复杂度会大幅下降。 为说明这一点，我们引入字符串 `x` 的结构集 `Sx = {(i, j) | ∃A ∋ x, C(A) ≤ i, log |A| ≤ j}`，它可由两个“边界线”函数 `hx(i)` 和 `gx(j)` 识别。其中，`hx(i)` 称为 `x` 的柯尔莫哥洛夫结构函数，对于小的 `i`，可能因缺乏低复杂度模型而取无穷大值；而 `gx(j)` 对所有 `x` 都是全函数。 每个长度为 `n` 且柯尔莫哥洛夫复杂度为 `k` 的字符串 `x` 的结构集 `Sx` 具有以下三个性质（以 `gx` 函数表述）： 1. `gx(0) = k + O(1)`（由 `A = {x}` 见证）。 2. `gx(n) = O(log n)`（由 `A = {0, 1}ⁿ` 见证）。 3. `gx` 是非递增的，且对于任意 `j, l ∈ N`，有 `gx(j + l) ≥ gx(j) - l - O(log l)`。 充分统计量对应于 `Sx` 中 `i + j ≈ k` 的 `(i, j)`，直线 `i + j = k` 因此被称为充分性线。 存在这样的字符串，其结构函数难以确定何时离开充分性线。例如，固定大的 `n`，令 `k = n/2`，`g(j) = max{k - jk/(k + α), 0}`（其中 `α = α(k) ≤ k` 是 `k` 的可计算函数且取自然值），则存在长度为 `n` 且复杂度为 `k + O(log n)` 的字符串 `x`，其 `gx(j) = g(j) + O(log n)`。对于这样的字符串，最小 `c` - 充分统计量的复杂度为 `k - (c + O(log n)) · k/α`，且作为 `c` 的函数快速下降。