邮政通信问题

在本节中，我们将讨论字符串的不可判定性，而不是图灵机。字符串的不可判定性是借助邮政对应问题 (PCP) 确定的。让我们定义 PCP。

“邮政对应问题由输入上的两个等长字符串列表组成。这两个列表是 A = w₁, w₂, w₃, .... , w_n 和 B = x₁, x₂, x₃, .... x_n，然后存在一个非空整数集合 i₁, i₂, i₃, .... , in，使得，
w₁, w₂, w₃, .... w_n = x₁, x₂, x₃, .... x_n"

为了解决邮政对应问题，我们尝试所有 i₁, i₂, i₃, .... , in 的组合，找到 w1 = x1，然后我们说 PCP 有一个解决方案。

示例 1

考虑如下给出的对应系统

A = (b, bab³, ba) 和 B = (b³, ba, a)。输入集为 ∑ = {0, 1}。找到解决方案。

解决方案

解决方案是 2、1、1、3。这意味着 w₂w₁w₁w₃ = x₂x₁x₁x₃

从这两个列表中构造的字符串是 bab³b³a。

示例 2

具有两个列表 x = (b, a, aba, bb) 和 y = (ba, ba, ab, b) 的 PCP 有解决方案吗？

解决方案： 现在我们必须找出这样一个序列，即由 x 和 y 形成的字符串是相同的。这样的序列是 1、2、1、3、3、4。因此，从 x 和 y 的列表中

示例 3

获得以下邮政对应问题的解。 A = {100, 0, 1}, B = {1, 100, 00}

解决方案： 考虑序列 1、3、2。从 A 获得的字符串 = babababb。从 B 获得的字符串 = bababbbb。这两个字符串不相等。因此，如果我们尝试来自这两个集合的各种组合来找到唯一的序列，我们将无法获得这样的序列。因此，此系统没有解决方案。

示例 4

获得以下邮政对应问题的解决方案，X = {100, 0, 1}, Y = {1, 100, 00}。

解决方案： 解决方案是 1、3、1、1、3、2、2。 字符串是

X1X3X1X1X3X2X2 = 100 + 1 + 100 + 100 + 1 + 0 + 0 = 1001100100100
Y1Y3Y1Y1Y3Y2Y2 = 1 + 00 + 1 + 1 + 00 + 100 + 100 = 1001100100100