PCP 可以识别吗？
Is PCP recognizable?
我想知道 Post Correspondence Problem(PCP) 是否可以识别。我学会了如何证明 PCP 的不可判定性。我也想过使用类似的方法来提高可识别性，即考虑 MPCP 并显示它是否可识别。我不确定这是否是一个好方法。
Post对应题确实是可以识别的。这里有四种查看方式：
为其构建一个识别器。给定一组图块，您可以想象一个 TM 列出恰好一个多米诺骨牌的所有序列，然后恰好两个多米诺骨牌，然后恰好是三个多米诺骨牌，然后恰好是四个多米诺骨牌，等等，每次逐渐增加多米诺骨牌的数量。如果 TM 发现了一系列顶部和底部匹配的多米诺骨牌，那么它可以接受。否则会无限循环。
为其构建一个非确定性 TM。 设计一个非确定性 TM，给定一组图块，非确定性地猜测要排列的一系列图块，然后检查顶部和底部是否匹配。如果是，它接受；否则它拒绝。然后，此 NTM 将接受任何“是”实例，因为它始终可以猜出一系列有效的多米诺骨牌，并且不会接受任何“否”实例，因为它永远无法猜出多米诺骨牌的有效顺序。
为其构建一个枚举器。 运行 对所有 tile 字符串的无限 trie 进行广度优先搜索。对于每一串瓷砖，如果顶部的字符串与底部的字符串匹配，则输出它。
为它建立一个验证器。输入是一组瓦片和一个可能的瓦片串。验证器检查该字符串中的所有图块是否都在图块集中，以及图块顶部和底部行上的字符串是否匹配。
我想知道 Post Correspondence Problem(PCP) 是否可以识别。我学会了如何证明 PCP 的不可判定性。我也想过使用类似的方法来提高可识别性，即考虑 MPCP 并显示它是否可识别。我不确定这是否是一个好方法。
Post对应题确实是可以识别的。这里有四种查看方式：
为其构建一个识别器。给定一组图块，您可以想象一个 TM 列出恰好一个多米诺骨牌的所有序列，然后恰好两个多米诺骨牌，然后恰好是三个多米诺骨牌，然后恰好是四个多米诺骨牌，等等，每次逐渐增加多米诺骨牌的数量。如果 TM 发现了一系列顶部和底部匹配的多米诺骨牌，那么它可以接受。否则会无限循环。
为其构建一个非确定性 TM。 设计一个非确定性 TM，给定一组图块，非确定性地猜测要排列的一系列图块，然后检查顶部和底部是否匹配。如果是，它接受；否则它拒绝。然后，此 NTM 将接受任何“是”实例，因为它始终可以猜出一系列有效的多米诺骨牌，并且不会接受任何“否”实例，因为它永远无法猜出多米诺骨牌的有效顺序。
为其构建一个枚举器。 运行 对所有 tile 字符串的无限 trie 进行广度优先搜索。对于每一串瓷砖，如果顶部的字符串与底部的字符串匹配，则输出它。
为它建立一个验证器。输入是一组瓦片和一个可能的瓦片串。验证器检查该字符串中的所有图块是否都在图块集中，以及图块顶部和底部行上的字符串是否匹配。