我认为，具有代表性的“不可判定问题”实例可以帮助思考“不可判定问题”的本质。

图灵在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 :

L2 : 

序列 (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 :

L2 :

波斯特对应问题（PCP）：判定给定字母表A是否存在两个长度相同匹配的字符串表L1和L2。PCP是“不可判定问题”，即不存在算法求解任意的PCP实例。

PCP不可判定性的最常见证明描述一个PCP 实例，它可以模拟一个图灵机对特定输入的计算。当且仅当图灵机接受输入时，匹配才会发生。因为判定图灵机是否接受输入是一个基本的不可判定问题，所以PCP是不可判定问题。

参考文献：

https://en.wikipedia.org/wiki/Post_correspondence_problem