波斯特對應問題

波斯特對應問題（英語：Post correspondence problem）是美國數學家埃米爾·波斯特（Emil Post）於1946年提出的一個不可判定問題。^[1]

問題

已知字母表${\displaystyle A}$是包含至少兩個字符的有限集合。${\displaystyle A}$上的一個字符串是指由${\displaystyle A}$中字符組成的一個有限序列。假設${\displaystyle \alpha _{1},\ldots ,\alpha _{N}}$和${\displaystyle \beta _{1},\ldots ,\beta _{N}}$是由${\displaystyle A}$上的字符串所組成的兩個相同長度的表。如果存在一個序列${\displaystyle (i_{k})_{1\leq k\leq K}}$（${\displaystyle K\geq 1}$，且對所有${\displaystyle k}$都有${\displaystyle 1\leq i_{k}\leq N}$），使得

${\displaystyle \alpha _{i_{1}}\ldots \alpha _{i_{K}}=\beta _{i_{1}}\ldots \beta _{i_{K}}}$

成立，那麼就稱${\displaystyle A}$上的這兩個字符串表匹配。判定一個字母表上的任意兩個長度相同的字符串表是否匹配的問題即是波斯特對應問題。

示例

已知如下兩個字符串表：

α1 α2 α3 a ab bba

β1 β2 β3 baa aa bb

序列 (3, 2, 3, 1) 是這一波斯特對應問題的一個解：

${\displaystyle \alpha _{3}\alpha _{2}\alpha _{3}\alpha _{1}=bba+ab+bba+a=bbaabbbaa=bb+aa+bb+baa=\beta _{3}\beta _{2}\beta _{3}\beta _{1}.}$

bba bb i1 = 3

ab aa i2 = 2

bba bb i3 = 3

a baa i4 = 1

將上述序列重複任意多次（例如：重複兩次為 (3, 2, 3, 1, 3, 2, 3, 1)）得到的序列也都是此問題的解。

但如果兩個字符串表僅由${\displaystyle \alpha _{2},\alpha _{3}}$ 和 ${\displaystyle \beta _{2},\beta _{3}}$組成，那此時解便不存在。這是由於${\displaystyle \alpha _{2},\alpha _{3}}$ 的倒數兩個字符都是不同的，而${\displaystyle \beta _{2},\beta _{3}}$則都是由相同的兩個字符組成的。

不可判定性證明思路

對波斯特對應問題不可判定性的證明，一種最常見的思路是：先證明對一個圖靈機${\displaystyle M}$及輸入${\displaystyle \omega }$都能構造出波斯特對應問題的一個實例，使得匹配就是${\displaystyle M}$在${\displaystyle \omega }$上的接受計算歷史。如果能判定這個波斯特對應問題的實例是否有匹配的話，那圖靈機是否接受輸入的問題也就是可判定的了。由於圖靈機的接受問題是個基本的不可判定問題，於是可以說明波斯特對應問題也同樣是不可判定的。^[2]

參考文獻

1. E. L. Post. A variant of a recursively unsolvable problem (PDF). Bull. Amer. Math. Soc. 1946, 52.
2. Michael Sipser. A Simple Undecidable Problem. Introduction to the Theory of Computation 2nd. Thomson Course Technology. 2005: 199–205. ISBN 0-534-95097-3.