标签：自动机Post通信

2020-02-14半瓶木阅读(1269)评论(0)赞(0)

在本节中，我们将讨论字符串的不确定性，而不是图灵机的不确定性。字符串的不确定性借助Post的对应问题（PCP）来确定。让我们定义PCP。 “该帖子的对应问题由两个在输入上长度相等的字符串列表组成。这两个列表分别是A = w1，w2，w3，&...