Post 对应问题 | Codeboy's Blog

形式陈述

Post 对应问题的实例是有限多张牌

\left(\frac{u_1}{v_1},\ldots,\frac{u_k}{v_k}\right), \qquad u_i,v_i\in\Sigma^+.

问题询问是否存在长度 $m\ge1$ 的指标序列 $i_1,\ldots,i_m$ （允许重复），使

u_{i_1}\cdots u_{i_m}=v_{i_1}\cdots v_{i_m}.

在含至少两个符号的字母表上，该判定问题不可判定；常见证明从图灵机接受计算或修改版 PCP 作映射归约。要求非空序列，否则空连接会让所有实例平凡成立。

直觉

PCP 把一串局部选择积累成两个必须完全相同的全局字符串：每次选择同一张骨牌，同时向上、下两行追加不同片段。选择序列可以任意长且所需长度无法预先界定，因此有限骨牌集仍能让局部选择承载无界计算历史。表面上它只是字符串拼接谜题，困难恰来自要在某个未知长度上使两条全局拼接完全同步。

例子与边界

牌 $(a/ab),(ba/a)$ 选择序列 $1,2$ 时，上串为 $aba$ 、下串也为 $aba$ ，所以有解。另一个实例是骨牌 $(ab,a)$ 与 $(b,bb)$ ：选择序列 $1,2$ 得到的上串和下串都是 abb。

搜索所有长度为 $1,2,3,\ldots$ 的有限序列能半判定“有解”：找到匹配便停止；若无解，搜索可能永远不会产生可确认的终点。不同教材允许空字符串或规定首牌的变体；这些版本之间需显式归约，不能在不改证明时混用。

限制序列长度为给定 $k$ 后，问题变成有限穷举并可判定；固定一元字母表等特殊情形也可能简化。不可判定性针对一般有限字母表与无界重复，不能由“每张牌数量有限”误推为状态空间有限。

本页语境中的 PCP 是 Post correspondence problem。复杂性理论也把概率可检验证明简称为 PCP，但后者讨论随机验证者对证明 oracle 的局部查询；两个概念没有前置关系，检索时应使用完整名称或各自的规范 ID。

推论与应用

PCP 是从图灵机计算历史到字符串匹配的经典编码目标，也是证明文法歧义、CFG 交非空、矩阵与字符串系统不可判定性的通用中介；这些证明通常使用映射归约。它与形式语言理论的联系尤其紧密：局部拼接约束足以模拟相邻配置一致性，展示了只有有限牌和字符串连接的朴素词组合问题如何获得通用计算能力。

参考资料

Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Ch. 5, Post correspondence problem and undecidability reductions。
Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability, MIT Press, 1987，Chs. 12–13, correspondence systems and recursively enumerable sets。