On the Complexity of the Bi-infinite Post Correspondence Problem

技术摘要：论双无限 Post 对应问题（Bi-infinite Post Correspondence Problem）的复杂性

问题定义
本文研究了双无限 Post 对应问题（ZPCP）的计算复杂性。经典的 Post 对应问题（PCP）要求寻找一个非空有限词 $w$，使得对于给定的两个态射 $g$ 和 $h$，满足 $g(w) = h(w)$；而无限 PCP（$\omega$PCP）则寻求一个无限词；ZPCP 则询问是否存在一个双无限词 $\alpha = \dots a_{-1}a_0a_1 \dots$，使得 $g(\alpha) = h(\alpha)$。至关重要的是，双无限词的相等定义是基于偏移量的：若存在一个整数偏移 $\tau$，使得 $g(\alpha)$ 在位置 $i$ 处的字母等于 $h(\alpha)$ 在位置 $i+\tau$ 处的字母，则称 $g(\alpha) = h(\alpha)$。

前人的工作已经确定 ZPCP 是不可判定的，且属于算术层级中的 $\Sigma^0_2$ 类，但尚未将其严格定位在层级中（即尚不清楚它是 $\Pi^0_1$-完全还是严格处于第 2 层）。本研究的主要目标是确定 ZPCP 在算术层级中的确切位置。

方法论
作者建立了一套从确定性图灵机（TM）在空输入上的非停机问题出发，经过半 Thue 系统，最后到达 PCP 变体的还原链。该方法论依赖于以下几个关键的技术构造：

1. 可逆半 Thue 系统： 作者从给定的图灵机 $M$ 构建了一个特定的半 Thue 系统 $S_M$。该系统被设计为既是 $\Theta$-确定性的，又是 $\Theta$-可逆的。可逆性对于向 ZPCP 的最终还原至关重要，因为它允许在正向和反向两个方向上模拟计算步骤。
2. 单射态射与有界延迟： 本文构造了模拟该半 Thue 系统的态射 $g$ 和 $h$。一个重要的技术贡献是证明了这些态射具有“有界延迟 2”，这意味着它们是单射的。这使得作者能够将不可判定性结果扩展到单射态射类。
3. 偏移变体： 作者定义并分析了“$s$-偏移”变体问题（$\omega$PCP$_s$ 和 ZPCP$_s$），其中相等条件被固定为一个特定的偏移量 $s$。他们证明了这些变体是 $\Pi^0_1$-完全的。
4. 去同步化与加划线处理： 为了处理 ZPCP 的双无限特性并消除平凡解，作者采用了一种复杂的字母表构造，涉及符号的有划线版本和无划线版本，以及特定的“去同步化”标记（$d^4$ 和 $f^4$）。这迫使任何解都必须在正向和反向配置之间交替，从而有效地模拟半 Thue 系统在两个方向上的推导。

核心贡献与结果

• $\omega$PCP 的复杂性： 作者证明，即使在限制为单射态射（具体为有界延迟 2 的态射）的情况下，无限 PCP（$\omega$PCP）仍然是不可判定的。此外，他们确定了这一受限版本是 $\Pi^0_1$-完全的。
• 偏移问题的复杂性： 本文证明，对于任何自然数 $s$，$s$-偏移无限 PCP（$\omega$PCP$_s$）和 $s$-偏移双无限 PCP（ZPCP$_s$）都是 $\Pi^0_1$-完全的。
• ZPCP 的复杂性： 主要结果涉及标准的 ZPCP。作者证明 ZPCP 是 $\Pi^0_1$-困难的。结合已知 ZPCP 属于 $\Sigma^0_2$ 且不属于 $\Pi^0_1$，以及由于其 $\Pi^0_1$-困难性而得出的它不属于 $\Sigma^0_1$ 的新证明，他们得出结论：
  $$\text{ZPCP} \in \Sigma^0_2 \setminus (\Pi^0_1 \cup \Sigma^0_1)$$
  这将其严格置于算术层级的第二层。
• 半 Thue 系统： $\Theta$-确定性和 $\Theta$-可逆半 Thue 系统的非终止问题被证明是 $\Pi^0_1$-完全的。

意义与主张
本文声称深化了对 Post 对应问题变体复杂性格局的理解。具体而言：

• 它解决了关于 ZPCP 在算术层级中位置的歧义，确认了它不是 $\Pi^0_1$-完全，而是严格位于第 2 层。
• 它表明，即使在单射性和有界延迟等强约束下（这些约束通常用于简化判定问题），无限变体的不可判定性和 $\Pi^0_1$-完全性依然存在。
• 作者指出，虽然他们已将 ZPCP 定位于第 2 层，但 ZPCP 是否为 $\Sigma^0_2$-完全仍是一个开放问题。

这项工作依赖于从图灵机非停机到半 Thue 非终止，再到各种 PCP 变体的严谨还原序列，并利用所构造系统的可逆性来处理双无限约束。