波斯特對應問題

一個用骨牌做成的拼圖

到現在你已經養成了歸約的習慣：要證明一個新問題辦不到，你就找一個已知辦不到的問題，把它翻譯成這個新問題，並且始終小心箭頭朝哪個方向走。到目前為止，那個已知辦不到的問題一直是停機問題（或它的表親 A_TM）。但要把「這台圖靈機會不會停？」翻譯成、比方說、一個關於文法的問題，是很彆扭的——你得把一整台機器的行為編碼進一個文法裡。如果我們先把停機問題洗成一個更清爽、更組合化的形式，事情就容易得多。那個更清爽的形式就是波斯特對應問題（Post correspondence problem），簡稱 PCP，而它看起來一點也不像機器。它看起來像個孩子的拼圖。

拼圖是這樣的。給你一批有限的骨牌，每張骨牌的上面寫著一個字串、下面寫著另一個字串——兩者都取自某個字母表 Sigma（你被允許使用的那有限一池符號）。每一種骨牌你都有用不完的存貨。你的任務是把它們排成一列，可以重複使用，使得把所有上面的字串由左讀到右拼出來的字串，恰好等於把所有下面的字串由左讀到右拼出來的字串。這樣一個序列稱為一個對應（match）。PCP 問的只是：對這一批特定的骨牌，到底存不存在任何一個對應？

Dominoes:   d1 = [ b  / ca ]   d2 = [ a  / ab ]   d3 = [ ca / a  ]   d4 = [ abc / c ]
            (top / bottom)

Try the sequence  d2  d1  d3  d3  d4 :

   tops:    a   b    ca   ca   abc      ->  concatenated:  a b ca ca abc  =  abcacaabc
   bottoms: ab  ca   a    a    c        ->  concatenated:  ab ca a a c    =  abcacaabc

           MATCH:  top string == bottom string == "abcacaabc"

一個有對應的具體 PCP 實例。注意每張骨牌的上下字串長度不同，所以必須最終吻合的是那不斷累積的總和——一場精細的記帳遊戲。

為什麼它比看起來更難

你很容易以為，只要按長度依序試遍所有序列就好：先試所有長度 1 的對應，再試長度 2 的，依此類推，找到一個就停。確實可以這麼做——但只有在對應存在時才行。若對應真的存在，這個暴力搜尋遲早會撞上它，於是你可以大喊「是」。麻煩在「否」的那一邊。若沒有任何對應存在，就沒有任何一個長度能讓你安心停止搜尋，因為你還沒試到的下一個序列，說不定正是那一個。搜尋會永遠跑下去，卻永遠掙不到回答「否」的資格。這正是「可辨識但不可判定」這類問題的特徵——可辨識，因為「是」的實例遲早會自己現身；不可判定，因為「否」的實例永遠不會。

這份不可判定性是從哪兒來的？它是被一個映射歸約從停機問題（技術上是從 A_TM，即接受問題）偷渡進來的。構造手法很巧妙：給定一台機器 M 和一個輸入 w，你打造一批骨牌，設計得如此巧妙，以致讓上排對上下排的唯一辦法，就是一步一步拼出 M 在 w 上執行的整串組態（configuration）——所謂的「接受計算歷史」。下排始終被迫恰好領先上排一個組態，就像同一個故事被講兩遍，而下面那位旁白者永遠落後一句，直到最後一張骨牌——只有當 M 抵達它的接受狀態時，它才能把這道缺口補上。

把這個歸約讀對方向

對方向務必極其慎重，因為這正是本階第一篇所警告的那個陷阱。我們是把停機問題歸約到 PCP。那支箭頭的意思是：「假如我手上有一台 PCP 求解器，我就能解停機問題。」這位翻譯員把每一個停機問題都轉成一批骨牌，使得 M 接受 w 若且唯若那批骨牌有對應。於是一台 PCP 神諭就能解決每一個停機問題——但我們已經證明停機問題無法被解決。所以 PCP 求解器並不存在。不可判定性是從那個已知很難的停機問題流入 PCP，絕不是反過來。倘若你反而把 PCP 歸約到停機問題，你頂多學到 PCP 不會比停機更難——一個真確卻無用的事實，對 PCP 的難度毫無證明力。

從一個你已知不可判定的問題出發。這裡是：A_TM——機器 M 是否接受輸入 w？（本階梯稍早已證其不可判定）。
造一個可計算的翻譯員 f。給定資料對 (M, w)，f 輸出一批骨牌——而 f 自己總是會停機；它只是一份誠實的構造配方，並非求解器。
把等價關係兩個方向都證出來：那批骨牌有對應，若且唯若 M 接受 w。是對應到是、否對應到否——這份雙向的忠實性，正是它之所以成為映射歸約的緣由。
用反證法收尾：把 PCP 的判定器和 f 接起來，就能判定 A_TM。既然 A_TM 不可判定，PCP 也必定不可判定。難度已經被轉移過來了。

我們為何要費這功夫：PCP 撂倒那些文法問題

回報來了。PCP 不是終點，而是一塊踏腳石。既然我們手上握有一個乾淨、不含機器的不可判定問題，每當目標本身是組合性的——而文法正是如此——它就成了最理想的「歸約自」對象。一整族的不可判定文法問題幾乎是機械地從 PCP 掉出來，因為把一批骨牌編碼進一個上下文無關文法，遠比把一台圖靈機編碼進去來得自然。竅門是造兩個文法（或一個文法的兩半）——一個生成骨牌序列所有的「上排」讀法，一個生成所有的「下排」讀法——使得某個字串恰好在它見證一個 PCP 對應時，才同時屬於這兩個語言。

這一個念頭就撂倒了好幾個著名問題。一個上下文無關文法是否有歧義——是否有某個字串擁有兩棵不同的剖析樹？——是不可判定的，因為一個 PCP 對應就給了你一個能用兩種方式導出的字串。兩個上下文無關語言的交集是否為空，是不可判定的，因為非空的交集就是一個對應。一個上下文無關文法是否生成其字母表上的每一個字串（普遍性）也是不可判定的。從盯著文法看，這些都不顯然；它們全都是在 PCP 把「該歸約自的對象」遞到我們手上之後，才變得看得見。這就是 PCP 的日常角色：一個可重複使用的難度來源，每用一次，不可判定性就被往下轉移一回。