波斯特對應問題（Post correspondence problem）
/ post (as in the surname) /
想像一盒特殊的骨牌。每張骨牌有上方字串與下方字串，像一張卡片上面寫「ab」、下面寫「a」。你可以隨意重複使用任何骨牌，把它們排成一列。若把所有上方字串由左到右讀出，得到的字串與把所有下方字串讀出的字串一模一樣，你就贏了。波斯特對應問題（Post correspondence problem, PCP）問的是這個看似簡單的問題：對給定的一盒骨牌，是否存在任何一種獲勝的排列？
形式上，一個實例是某字母表上的有限對字串清單 (t1, b1), ..., (tk, bk)。一個解是一個非空的索引序列 i1, i2, ..., in（允許重複），使得串接 t_{i1} t_{i2} ... t_{in} 等於串接 b_{i1} b_{i2} ... b_{in}。例如骨牌 (a, ab), (b, ca), (ca, a), (abc, c)，序列 1, 2, 3, 1, 4 讓上下方都拼出 abcaaabc，所以它是個解。困難之處在於：獲勝序列可能需要多長並無上界，而不斷嘗試越來越長的排列，永遠無法讓你斷言「沒有解」。PCP 不可判定：沒有演算法能對每一盒骨牌判定是否可能配對成功。
為何要在意一個骨牌謎題？因為 PCP 是證明「文法」問題不可判定的大槓桿。PCP 的不可判定性，是透過從接受／停機問題的歸約建立的（圖靈機的計算歷史可以編碼成一個骨牌配對任務），接著 PCP 再被歸約到上下文無關文法的問題。這條鏈正是我們得知以下事實的途徑：文法歧義不可判定、文法等價不可判定、某文法是否產生每個字串（全域性）不可判定、兩個上下文無關語言是否相交不可判定。PCP 居中，是連接機器不可判定與文法不可判定之間便利的組合學樞紐。一點細微之處：單一符號字母表上的 PCP，以及骨牌極少的 PCP，是可判定的；不可判定性需要足夠的空間。
骨牌（上／下）：(b, ca), (a, ab), (ca, a), (abc, c)。試序列 2, 1, 3, 2, 4：上方得 a b ca a abc = abcaaabc；下方得 ab ca a ab c = abcaaabc。兩者相符，所以這個實例有解。換一盒骨牌時，要判定是否「存在」任何這樣的配對序列，一般而言是不可能的。
排列骨牌使上方字串與下方字串拼出同一個字；PCP 問這是否曾有可能。
PCP 一般而言不可判定，但並非永遠如此：在單一符號字母表上它可判定，骨牌極少的實例也可判定。不可判定性指的是符號與牌數足夠的一般問題。