turing-machines - PCP 可以识别吗？

Question

我想知道邮政通信问题 (PCP) 是否可识别。我学会了如何证明 PCP 的不可判定性。我也想过使用类似的方法来提高可识别性，即考虑 MPCP 并显示它是否可识别。我不确定这是否是一个好方法。

Answer 1

邮政通信问题确实是可以识别的。这里有四种查看方式:

1. 为其构建一个识别器。给定一组图 block ，您可以想象一个 TM 列出恰好一个多米诺骨牌的所有序列，然后正好是两个多米诺骨牌，然后正好是三个多米诺骨牌，然后正好是四个多米诺骨牌，依此类推，每次逐渐增加多米诺骨牌的数量。如果 TM 发现了一系列顶部和底部匹配的多米诺骨牌，那么它可以接受。否则会无限循环。

2. 为其构建一个非确定性 TM。设计一个非确定性 TM，给定一组图 block ，不确定地猜测要排列的一系列图 block ，然后检查顶部和底部是否匹配.如果是，它接受；否则它拒绝。然后，该 NTM 将接受任何"is"实例，因为它始终可以猜出一系列有效的多米诺骨牌，并且不会接受任何“否”实例，因为它永远无法猜出多米诺骨牌的有效顺序。

3. 为其构建一个枚举器。对所有图 block 字符串的无限 trie 运行广度优先搜索。对于每一串瓦片，如果顶部的字符串与底部的匹配，则输出它。

4. 为其构建一个验证器。输入是一组图 block 和一个可能的图 block 串。验证器检查该字符串中的所有图 block 是否都在图 block 集中，以及图 block 顶部和底部行上的字符串是否匹配。