在本节中，我们将讨论字符串的不确定性，而不是图灵机的不确定性。字符串的不确定性借助Post的对应问题（PCP）来确定。让我们定义PCP。
“该帖子的对应问题由两个在输入上长度相等的字符串列表组成。这两个列表分别是A = w1，w2，w3，…
，wn和B = x1，x2，x3，…
。xn，则存在一个非空的整数集i1，i2，i3，…
，这样w1，w2，w3，…
wn = x1，x2，x3，…
. xn”
【自动机Post通信问题】为了解决岗位对应问题，我们尝试将i1，i2，i3，…
的所有组合找出w1 = x1，然后说PCP有解决方案。
范例1：
考虑如下所示的通信系统
A =（b，bab3，ba）和B =（b3，ba，a）。输入集为∑ = {0，1}。找到解决方案。
解：
解为2、1、1、3。这意味着w2w1w1w3 = x2x1x1x3
这两个列表中构造的字符串都是bab3b3a。
文章图片
范例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
