我认为，具有代表性的“不可判定问题”实例可以帮助思考“不可判定问题”的本质。
图灵在1936年的论文中证明了“判定一阶谓词公式是否可证明的”是“不可判定问题”。
波斯特（Emil Post）于1946年提出一个更简单的不可判定问题：波斯特对应问题（Post correspondence problem）。
***
波斯特对应问题 - 不可判定问题
波斯特对应问题（Post Correspondence Problem，PCP）是美国数学家埃米尔·波斯特（Emil Post，1897-1954）于1946年提出的一个不可判定问题。
问题描述
已知字母表A是包含至少两个字符的有限集合，A上的字符串是由A中字符组成的有限序列。假设L1 = (a1,…an)和L2 = (b1,…bn)是由A中的字符串所组成的二个相同长度的表。如果存在一个序列 i1,…,ik，使得：ai1,…aik = bi1,…bik，则称字符串表 L1 和L2 匹配，并称这是此波斯特对应问题的实例的一个解。
实例1：
L1 :
a1 | a2 | a3 |
a | ab | bba |
L2 :
b1 | b2 | b3 |
bba | aa | bb |
序列 (3, 2, 3, 1) ，使得
a3a2a3a1 = bba+ab+bba+a = bbaabbbaa
= bb+aa+bb+baa = b3b2b3b1
所以，实例1有解。
实例2：
但如果两个字符串表仅由a2,a3和b2,b3组成：L1 = (a2,a3)和L2 = (b2,b3)，由于a2,a3的首尾两个字符不同，而b2,b3的首尾两个字符则相同，所以实例2有解。
L1 :
a2 | a3 |
ab | bba |
L2 :
b2 | b3 |
aa | bb |
波斯特对应问题（PCP）：判定给定字母表A是否存在两个长度相同匹配的字符串表L1和L2。PCP是“不可判定问题”，即不存在算法求解任意的PCP实例。
PCP不可判定性的最常见证明描述一个PCP 实例，它可以模拟一个图灵机对特定输入的计算。当且仅当图灵机接受输入时，匹配才会发生。因为判定图灵机是否接受输入是一个基本的不可判定问题，所以PCP是不可判定问题。
参考文献：
https://en.wikipedia.org/wiki/Post_correspondence_problem
转载本文请联系原作者获取授权，同时请注明本文来自柳渝科学网博客。
链接地址：https://wap.sciencenet.cn/blog-2322490-1385191.html?mobile=1
收藏
