波斯特对应问题

波斯特对应问题是 Emil Post 于 1946 年提出的不可判定问题。因为它比停机问题和 Entscheidungs 问题更简单，所以经常用于不可判定性的证明。

设 A {\displaystyle A} 是一个至少有两个符号的字母表。

那么判定问题就是判定这样的解是否存在。

这产生了在文献中经常发现的等效替代定义，根据该定义，任何两个同态 g , h {\displaystyle g,h} 具有公共域和公共辅域形成波斯特对应问题的实例，其中 现在询问域中是否存在非空词 w {\displaystyle w} 使得

g ( w ) = h ( w ) {\displaystyle g(w)=h(w)} 。

另一个定义很容易将此问题描述为一种谜题。 我们从一组多米诺骨牌开始，每张多米诺骨牌包含两根绳子，每边一根。 一个单独的多米诺骨牌看起来像

任务是列出这些多米诺骨牌（允许重复），以便我们通过读取顶部的符号得到的字符串与底部的符号字符串相同。 此列表称为匹配项。 Post Correspondence Problem 是判断一组多米诺骨牌是否有匹配。例如，下面的列表就是这个拼图的匹配。

对于某些多米诺骨牌集合，可能无法找到匹配项。

不能包含匹配项，因为每个顶部字符串都比对应的底部字符串长。

考虑以下两个列表：

这个问题的解决方案是序列 (3, 2, 3, 1)，此外，由于 (3, 2, 3, 1) 是一个解，所以它的所有重复项也是一个解，例如 (3, 2, 3, 1, 3, 2, 3, 1) 等； 也就是说，当存在一个解时，就会有无限多个这种重复的解。

然而，如果这两个列表只包含 α 2 , α 3 {\displaystyle \alpha _{2},\alpha _{3}} 和 β 2 , β 3 {\displaystyle \beta _{ 2},\beta _{3}} 来自这些集合，那么就没有解决方案（任何此类 α 字符串的最后一个字母与其前面的字母不同，而 β 仅构造相同字母的对 ).

查看波斯特应对问题实例的一种便捷方式是作为以下形式的块的集合

每种类型的块都有无限供应。

求解器对这三种块类型中的每一种都有源源不断的供应。 解决方案对应于将块彼此相邻放置的某种方式，以便顶部单元格中的字符串对应于底部单元格中的字符串。

例子2

再次使用块来表示问题的一个实例，下面是一个除了仅通过重复一个解决方案而获得的解决方案之外还有无限多个解决方案的示例。

在这种情况下，形式为 (1, 2, 2, . . ., 2, 3) 的每个序列都是一个解决方案（除了它们的所有重复之外）

PCP 不可判定性的最常见证明描述了一个 PCP 实例，它可以模拟任意图灵机对特定输入的计算。