跳转至

健忘图灵机的构造

错误原文（第 15 页，推论 1.1 的证明）

…… \(\mathbb{U}\) 通过扫描区间 \(L_{i}, \ldots, L_0, R_0, \ldots, R_i\) 常数遍，将区间 \(L_{i-1}, \ldots, L_0, R_0, \ldots, R_{i-1}\) 均置为半满。

按照教材上的构造，区间调整只能是下面两种情况：

  1. 区间 \(R_0, \ldots, R_k\) 是空的，而区间 \(R_{k+1}\) 至少是半满的，此时拿出 \(R_{k+1}\) 中一半的符号填充到 \(R_0, \ldots, R_k\) 中，使它们半满，并对区间 \(L_0, \ldots, L_k\) 做对称的调整；
  2. 上述情况的对称情况。

情况 1 发生时，若 \(R_{k+1}\) 只是半满的，那么调整完成后 \(R_{k+1}\) 变为空的，如果此时计数器从 0 翻转至 1 的比特位置是 \(i > k + 1\)，就无法调整 \(R_{k+1}\) 使之半满。

问题的根源在于区间调整的操作不是局部的，我们只能调整从中心位置出发的一段连续非半满区间，对散落在外的非半满区间则无能为力。

解决办法也比较简单：之前的构造中，每个区间包含 \(2\times 2^{i}\) 个格子，而希望在每一步能够将关心的区间（即计数器自增时翻转的比特位置对应区间）置为半满。现在将每个区间包含的格子数增加为 \(3\times 2^{i}\)，并在调整时将关心的区间置为 \(1/3\) 满 或 \(2/3\) 满即可。这个想法来自 Pippenger 和 Fisher（1979） 1，我们下面基于 Vollmer2 的教材详细叙述这个构造。

推论 1.1

设 \(T(n)\) 是时间可构造的，\(L\) 可在 \(T(n)\) 时间内被一台图灵机 \(\mathbb{M}\) 判定。一定存在常数 \(C\) 和在 \(C T (n) \log T (n)\) 时间内判定 \(L\) 的健忘图灵机 \(\mathbb{M}'\)。

证明： 依旧假设 \(\mathbb{M}\) 的工作带是双向无限的，并用 \(\mathbb{Z}\) 中的整数来给带子上的格子编号。进一步还可以假设 \(\mathbb{M}\) 在输入带和输出带上已经是健忘的：无非是用两条额外的工作带去模拟输入带和输出带。

现在来构造健忘图灵机 \(\mathbb{M}'\)。它的工作带与 \(\mathbb{M}\) 一一对应，而字母表中增加一个用于表示冗余信息的符号 \(\times\)。将 \(\mathbb{M}'\) 的每条工作带划分为若干区间，其中 0 号格子是中心区间，始终存储 \(\mathbb{M}\) 读写头指向的符号；其左右两侧依次是区间 \(L_0, R_0, \ldots, L_{\log T(n)}, R_{\log T(n)}\)，每个区间 \(R_i\) 包含编号在 \([1 + 3\times (2^{i} - 1), 3\times (2^{i+1} - 1)]\) 中的 \(3\times 2^{i}\) 个格子，而 \(L_i\) 包含与 \(R_i\) 对称的格子。

我们希望通过移动工作带上的内容来模拟读写头的移动，在此过程中，要保证每个区间是下面 4 种状态中的一种：

  • 全空：所有格子都是 \(\times\)
  • \(1/3\) 满：\(1/3\) 的格子中是 \(\times\) 以外的符号
  • \(2/3\) 满：\(2/3\) 的格子中是 \(\times\) 以外的符号
  • 全满：所有格子都不是 \(\times\)

把 \(1/3\) 满和 \(2/3\) 满的区间称为“好区间”，而全空和全满的区间称为“坏区间”。如果区间 \(X_i\) 是坏区间（这里 \(X\) 是 \(L\) 或者 \(R\)），而区间 \(X_{i+1}\) 是好区间，那么很容易将 \(X_i\) 调整为好区间：如果 \(X_i\) 全空，就拿出 \(X_{i+1}\) 中 \(1/3\) 的非 \(\times\) 符号放进 \(X_i\) 中，使之成为 \(2/3\) 满；如果\(X_i\) 全满，就拿出其中 \(2/3\) 的符号放入区间 \(X_{i+1}\)。不难看出这种调整可以用健忘的方式实现。

下面给出模拟 \(2^k\) 步读写头移动的算法，其中假设区间 \(L_k, \ldots, L_0, R_0, \ldots, R_k\) 都是好区间：

  1. 如果 \(k = 0\)，即只模拟一步，那么只需要将中心位置的符号移入 \(L_0\) 或 \(R_0\) 中的某个区间，并将另一个区间中最靠近中心的符号移入中心位置即可。（这一步也很容易以健忘方式实现）
  2. 如果 \(k > 0\)，那么先递归模拟 \(2^{k-1}\) 步，随后将区间 \(L_{k-1}\) 和 \(R_{k-1}\) 调整为好区间；上述过程再重复一次即可。

这个模拟算法具有下面的性质：

性质

如果模拟 \(2^k\) 步之前，区间 \(L_k, \ldots, L_0, R_0, \ldots, R_k\) 都是好区间，那么

  1. 模拟过程中读写头只会在区间 \(L_k, \ldots, L_0, R_0, \ldots, R_k\) 之内移动
  2. 模拟结束后区间 \(L_{k-1}, \ldots, L_0, R_0, \ldots, R_{k-1}\) 都是好区间
  3. 模拟结束后区间 \(L_k, R_k\) 的填充率最多改变 \(1/3\)。

利用归纳法很容易证明上面的性质，尤其要注意第 3 点保证了两次递归模拟之后的调整总是可以进行。

有了这个模拟算法，\(\mathbb{M}'\) 先将所有区间初始化为 \(1/3\) 满，然后调用 \(2^{\log T(n)}\) 步模拟算法即可。

设模拟 \(2^k\) 步的时间是 \(T(k)\)，那么 \(T(k) = 2 T(k-1) + O(2^k)\)，这后一项是调整区间的耗时。不难看出 \(T(k) = O(k\cdot 2^k)\)，因此模拟 \(2^{\log T(n)}\) 步的时间就是 \(O(T(n)\log T(n))\).

致谢

感谢王文茜同学在 2023 年秋季学期的课上指出了这个问题。

  1. Nicholas Pippenger and Michael J. Fischer. 1979. Relations Among Complexity Measures. J. ACM 26, 2 (April 1979), 361–381. DOI:https://doi.org/10.1145/322123.322138 ↩

  2. Heribert Vollmer. 1999. Introduction to circuit complexity: a uniform approach. Springer, Berlin ; New York, 36-40. ↩