動機
Post 對應問題的一個實例由若干對有限字串構成。問題是:能否取出由若干骨牌對組成的非空序列,將它們連接起來,使上串與下串相等。這個看似簡單的相等性問題,卻能編碼一整個圖靈機(Turing machine)的計算過程:一側列出各個格局,另一側列出它們的後繼格局。
我們分兩個階段證明這個歸約。先考慮修改版問題:它要求指定的一塊骨牌必須最先使用,其初始的不匹配恰好給出機器的第一個格局。隨後,透過一個標記符構造去除這項要求,得到所有骨牌字串均非空的普通實例。
定義
定義 5.4.1
(Post 對應問題與修改版)
PCP 骨牌是有限字母表上一對非空字串 。一個解是一個非空的下標序列 ,滿足 。骨牌可以重複使用。修改版 PCP(MPCP)另外要求 。
定義 5.4.2
(規範化的機器與格局)
我們從確定型圖靈機的接受問題出發進行歸約,該問題的不可判定性已在可計算性一章中證明。這裏採用標準的等價模型:帶為半無限,存在一個讀寫頭永不越過的左邊界,有限的帶字母表包含空白符,並且接受狀態與拒絕狀態是互不相同的停機狀態。接受狀態沒有普通的轉移。狀態符號與帶符號取自互不相交的有限字母表,分隔符與結束標記符均為全新符號。一個格局是一個有限的非空帶字串,其中恰有一個狀態符號,緊接在被掃描的帶符號之前。除非需要用來表示被掃描的單元格,否則可以省略末尾的空白符。
定理
定理 5.4.3
(修改版對應問題的不可判定性)
存在一個可計算的變換,把一部機器及其輸入變為一個骨牌字串均非空的 MPCP 實例,使得該實例有解當且僅當機器接受該輸入。
定理 5.4.4
(骨牌非空的 PCP 的不可判定性)
骨牌字串均非空的 MPCP 可以有效地歸約到骨牌字串均非空的普通 PCP。因此,即使在這項非空約定下,普通 PCP 仍然不可判定。
半無限且帶受保護邊界的機器模型是標準的等價圖靈模型;本章把這個模型等價性事實作為先修結論使用。每個狀態、帶符號和全新的標記符都在有限的對應字母表中編碼。兩個定理的證明如下:先構造骨牌,再給出正確性的兩個方向,最後分析標記符變換。
證明
計算歷程的骨牌
固定機器 與輸入 。令 為其初始格局(若輸入為空,則含一個空白符)。引入全新的分隔符 與結束標記符 ,二者均不出現在帶字母表與狀態字母表中。指定的首塊骨牌為
它的下串比上串多出一個格局和一個分隔符。對每個帶符號 加入複製骨牌 ,並加入分隔符骨牌 。不要為狀態符號加入複製骨牌。
對於「在狀態 下掃描 ,寫入 ,進入狀態 並向右移動」的轉移,加入 。同時加入右邊界版本 ,其中 表示空白帶符號。後者在讀寫頭移出已表示的右端時,明確地產生一個被掃描的空白符。
對於「寫入 ,進入 並向左移動」的轉移,對每個帶符號 加入 。這使狀態標記符移到前一個單元格,同時保持該單元格的符號不變。受保護的左邊界約定保證合法的轉移永遠不需要用到左側未表示的單元格。
對於接受狀態 和每個帶符號 ,加入清理骨牌 與 。最後加入結束骨牌
所有骨牌分量均非空。清理骨牌並不是機器的步驟;它們只允許在接受狀態出現之後使用,並逐步刪去接受狀態周圍的帶符號。
由接受運行得到解
證明
(接受運行給出解)
使用強制的首塊骨牌之後,上串為 ,下串為 。設上串已追上到某個格局 之前的分隔符,而下串還多出後綴 。對遠離狀態標記符的帶符號使用複製骨牌,在標記符處使用一塊合適的轉移骨牌。於是上串追加 ,下串追加其後繼格局及分隔符。
對於在已表示的右端向右移動的情形,使用邊界骨牌在新狀態之後追加一個空白符。對於向左移動的情形,含有前一個帶符號的骨牌把狀態標記符移到正確的位置。重複這個過程,就可以跟隨有限的接受計算的每一步。
一旦 出現,就在相繼的格局副本上使用清理骨牌,每次刪去相鄰的一個帶符號。最終多出的格局僅餘 。結束骨牌使上串追加 ,下串追加 ,於是累積起來的兩個字串相等。
由解得到接受運行
證明
(解給出接受運行)
在任何結束骨牌之前,下串恰好比上串多一個分隔符 。第一塊骨牌之後即是如此,而每塊複製、轉移和清理骨牌在兩側含有的分隔符個數相同。因此,沒有結束骨牌就不可能相等。
標記符 只出現在結束骨牌中。在兩個相等的連接串中,該標記符的首次出現必須對齊。去掉第一塊結束骨牌之後的所有骨牌,得到一個以該骨牌結尾的解。在它之前,相等性迫使上串依次重現下串的初始格局塊以及隨後的每個格局塊。
被複製的塊恰含一個狀態符號。由於狀態符號沒有複製骨牌,掃描經過該符號時必須使用機器轉移骨牌或接受清理骨牌。周圍的帶符號與分隔符原樣複製。因此,在接受之前,每個完整的下一個塊都是合法的後繼格局。末端的右移可以明確地加入空白符;若省略了末尾的空白符,那麼除非該狀態是接受狀態(此時機器已經接受),否則只會在分隔符之前產生一個無法處理的狀態。向左邊界的移動已被規範化的機器模型排除。
清理骨牌只能在狀態符號 出現之後使用。它們保留該狀態並刪去相鄰的帶符號。只有當尚未匹配的格局已被化簡為 時,結束骨牌才能匹配。因此任何解都是透過一個合法的計算到達接受狀態的。拒絕停機或不接受的畸形邊界無法被閉合。
該構造只有有限塊骨牌,並且可由 計算得出:它枚舉有限的轉移表和帶字母表,並為每條規則寫出一個有限字串。這就證明了 MPCP 不可判定:若存在這類實例的判定器,就能判定機器是否接受。
證明透視
各項設計選擇在何處被用到
論證依賴三項設計選擇,每一項都在可以指出的位置被用到。第一,除首塊與結束骨牌之外,每塊骨牌兩側的分隔符個數相同,所以下串恆比上串多一個分隔符,任何解都無法避開結束骨牌。第二,也是最不明顯的一點:不為狀態符號設複製骨牌。這把看似靜態的字串相等變成一條規則:每個格局塊都必須在其唯一的狀態符號處被改寫,於是相鄰的塊互為後繼格局。若加入狀態符號的複製骨牌,一個塊便可以越過狀態符號而不應用任何轉移,下一個塊就不再是合法的後繼格局。第三,標記符 只出現在結束骨牌中,而結束骨牌要求尚未匹配的塊恰為 。清理骨牌只為 而設,所以拒絕或不終止的計算無法收尾。
去除強制首塊的條件
定義 5.4.5
(標記符映射與變換後的實例)
設一個 MPCP 實例在字母表 上有非空骨牌 ,並指定第一塊骨牌。選取 之外的全新標記符 、 和 。對字串 ,定義
這兩個映射都保持連接運算,並且 。構造如下的普通 PCP 骨牌:
- 一塊特殊起始骨牌 ;
- 對原來的每塊骨牌 ,一塊普通骨牌 ;
- 一塊結束骨牌 。
每個分量都非空,因為原骨牌的字串非空,而新增的標記符字串也非空。
證明
(標記符變換下解的對應)
若 MPCP 實例有解 ,其公共連接串為 ,則依次使用特殊起始骨牌、普通骨牌 ,再用結束骨牌。上串為 ,下串為 ,二者相等。
反之,任何普通 PCP 的解必須以特殊起始骨牌開始:普通骨牌的上串以 開頭而下串以原字母表中的符號開頭,結束骨牌則以 與 開頭;只有特殊骨牌的兩側以同一個全新標記符開頭。在第一塊結束骨牌之前,相等的連接串中不可能出現第二塊特殊起始骨牌。每塊普通骨牌在兩側各增加偶數的長度,所以在起始骨牌之後,上串前綴的長度為奇數(),下串前綴的長度為偶數()。因此第二個 會在兩個字串中出現於奇偶性相反的位置,標記符無法對齊。
相等的解必須含有結束骨牌:若沒有它,按同樣的計算,整個上串的長度為奇數而整個下串的長度為偶數,二者不可能相等。在第一個 處,相等性迫使
其中 分別是由第一塊骨牌及隨後所選的普通骨牌下標所得的上串連接與下串連接。由於 且 是單射,所以 。對應的原下標序列以第一塊骨牌開始,並且解出了該 MPCP 實例。這就完成了到普通 PCP 的歸約。
反例模式
去掉首塊條件會改變答案
一個誘人的捷徑是:對同一組骨牌直接問普通問題,以為答案與 MPCP 相同。取字母表 與骨牌 、,並指定骨牌 。以骨牌 開頭的序列,上串以 開頭而下串以 開頭,兩側永遠不會一致,所以這個 MPCP 實例無解。但作為普通 PCP 實例,單塊骨牌的序列 已是解,因為 。兩個答案不同,所以必須做標記符變換。變換後得到起始骨牌 、普通骨牌 與 ,以及結束骨牌 。每個解都必須以起始骨牌開頭,而它的上串 與下串 在第三個符號不同,所以變換後的實例同樣無解,與該 MPCP 實例一致。
例題詳解
例題 5.4.6
(單個機器轉移)
若 有一個右移轉移:在狀態 讀到 ,寫入 並進入 ,則骨牌 把局部格局片段 替換為 。此時狀態標記符位於右側符號之前,前提是右側確有已表示的符號。
例題 5.4.7
(向左移動的轉移)
對於讀到 、寫入 並進入 的左移,若前一個帶符號為 ,則得到骨牌 。新的狀態標記符緊接在 之前,即新被掃描的符號。
例題 5.4.8
(標記符恆等式)
對 ,有 且 。因此 。末尾的標記符 使兩個錯位的編碼對齊。
例題 5.4.9
(單塊骨牌的 MPCP 解)
若指定的骨牌是 ,則它單獨就解出該 MPCP 實例。變換後的序列使用特殊起始骨牌,再用結束骨牌。其上串與下串都成為 。
例題 5.4.10
(一次完整的接受運行)
設機器只有一個轉移:在狀態 讀到 時,寫入 ,進入 並向右移動。輸入為 ,所以 ,帶字母表為 。用到的骨牌(寫成(上串,下串))如下:
- 首塊骨牌 ;
- 右邊界轉移骨牌 :讀寫頭移出了已表示的右端,所以必須明確寫出一個空白符;
- 複製骨牌 與 ;
- 清理骨牌 與 ;
- 結束骨牌 。
依次使用:首塊骨牌、邊界骨牌、、、、、、結束骨牌,則上串與下串都拼出
下串依次寫出格局 、、 與 ,上串落後一個格局逐步追上,最後由結束骨牌把 與單獨的 對齊。
概念視角算法
把解看成穿過「懸出部分」的路徑
把兩個部分連接中較長者超出較短者的部分稱為懸出部分。只有當兩個字串保持一致(其中一個仍是另一個的前綴)時才可以接上一塊骨牌,接上後得到新的懸出部分。於是一個解就是至少用一塊骨牌、從空的懸出部分出發又回到空的懸出部分的路徑。在上面完整的接受運行中,第一塊骨牌之後的懸出部分是 ,邊界骨牌之後是 ,而結束骨牌之後為空。
常見錯誤
常見錯誤
(以為每塊骨牌自身必須平衡)
一塊骨牌的上串與下串不必等長,只有在把整個非空序列連接起來之後才要求相等。計算構造刻意讓下串一直領先一個格局,直到結束骨牌出現。
常見錯誤
(隨意複製狀態符號)
若隨意複製狀態符號,則一個格局可以在不應用任何轉移的情況下通過一輪掃描。狀態符號只由轉移骨牌或接受清理骨牌處理,這就迫使計算具有預期的結構。
總結
MPCP 骨牌在一側編碼一個格局,在另一側編碼其後繼格局;接受狀態使清理與閉合成為可能。錯位標記符變換在普通 PCP 實例中強制使用指定的首塊骨牌,並保持骨牌字串非空。兩個歸約合在一起,由圖靈機接受問題證明了 PCP 不可判定。
練習
快速檢查
(在 MPCP 構造中,強制首塊骨牌在兩側各放置了甚麼?)
比較這塊骨牌上串與下串的內容。
解答 · 答案
上串為 ,下串為 ,所以下串領先了初始格局和一個分隔符。
快速檢查
(為甚麼機器的狀態符號沒有複製骨牌?)
想一想掃描經過狀態符號時允許做甚麼。
解答 · 答案
沒有狀態符號的複製骨牌,複製一個格局塊就必須在其唯一的狀態符號處使用轉移骨牌,或在接受之後使用接受清理骨牌。這就防止了不接受的格局被原樣複製並冒充為下一步。
快速檢查
(驗證 。)
先寫出 與 。
解答 · 答案
且 ,所以 ,而 ,兩側相等。
快速檢查
(為甚麼變換後的普通實例的解必須最先使用特殊起始骨牌?)
比較各類骨牌上串與下串的第一個符號。
解答 · 答案
普通骨牌的上串以 開頭而下串以原符號開頭,結束骨牌的上串以 開頭而下串以 開頭。只有特殊起始骨牌的兩側以同一個全新的 開頭,所以只有它能開始一對相等的連接串。