对应邮局问题

对应邮局问题 (PCP) 由 Emil Post 于 1946 年提出，是一个不可判定的判定问题。在字母表 ∑ 上的 PCP 问题陈述如下：

给定以下两个列表，**M** 和 **N**，它们包含在 ∑ 上的非空字符串：

M = (x₁, x₂, x₃,………, x_n)

N = (y₁, y₂, y₃,………, y_n)

如果对于某些 i₁,i₂,………… i_k，其中 1 ≤ i_j ≤ n，条件 x_i1 …….x_ik = y_i1 …….y_ik 成立，则可以说存在 Post 对应解。

示例 1

查找列表

M = (abb, aa, aaa) 和 N = (bba, aaa, aa)

是否存在 Post 对应解？

解答

这里：

x₂x₁x₃ = ‘aaabbaaa’

并且 y₂y₁y₃ = ‘aaabbaaa’

我们可以看到

x₂x₁x₃ = y₂y₁y₃

因此，解为 i = 2, j = 1, k = 3.

示例 2

查找列表 M = (ab, bab, bbaaa) 和 N = (a, ba, bab) 是否存在 Post 对应解？

解答

在这种情况下，不存在解，因为：

| x₂x₁x₃ | ≠ | y₂y₁y₃ | （长度不相等）

因此，可以说这个 Post 对应问题是不可判定的。