程式可以回答某些關於其他程式的問題。例如,執行一個程式並觀察到它停止,就證明這次執行會停機。但等待一段時間仍看不到它停止,不能告訴我們它日後會否停止。核心問題是:有沒有一個算法,能對所有情況給出答案,包括被模擬程式永遠運行的情況?
我們會在明確的計算模型下證明答案是否定,再用歸約證明另一個問題不可判定。這個結論不是說每個個案都很難,也不是說人永遠不能判斷某個具體程式的行為;它說的是,不存在一個對所有編碼個案都停機且答案正確的統一算法。
識別與判定不同
固定一套標準有效編碼,把圖靈機(Turing machine)寫成有限字串。我們能檢查字串在語法上是否有效編碼,也能逐步模擬一台機器。以 表示 的編碼,以 表示可有效解碼的機器與輸入配對。
定義 5.2.1
(判定器與識別器)
語言 的判定器對每個輸入都停機,並恰好接受 中的字串;對其餘字串停機並拒絕。 的識別器接受 的所有字串,也不會錯誤接受 以外的字串,但在 以外的輸入上可以永遠運行。
因此每個判定器都是識別器,但定義不要求識別器對否定個案發出訊號。「尚未接受」與「已拒絕」是不同的觀察。
定義 5.2.2
(停機語言)
停機語言是
這裏停機包括 接受或拒絕,並非只指接受。格式不正確的編碼不屬於此語言,可先經語法檢查而拒絕。
常見錯誤
(停機不等於接受)
容易把 讀成 接受的配對 所成的集合。但一台機器立即拒絕 時它已經停機,所以 。 接受的配對所成的集合是另一個語言。
例題 5.2.3
(識別器可以確認肯定個案)
給定有效配對 ,模擬 在 上的執行;一旦模擬停止便接受。當 真的停止,識別器最終會接受;若 永遠運行,識別器也會一直運行。它不會錯誤接受不停機的配對。這識別了 ,但下面會證明,不能把它修補成適用所有配對的判定器。
假設有完美判定器,再反轉它的答案
定理 5.2.4
(停機問題的不可判定性)
沒有判定器:不存在一台圖靈機,對每個輸入都停機,並恰好接受那些 在 上停機的字串 。
證明
(對角機與任何停機判定器矛盾)
反設存在判定器 :對每個有效配對 都停機,且恰在 於 上停機時回答「是」,否則回答「否」。
構造接受一個字串 的機器 :
- 若 不是有效的機器編碼,拒絕。
- 若 ,把配對 交給 。
- 若 回答「是」,永遠循環;若回答「否」,立即接受。
是合法機器:檢查編碼、構造配對及調用 均可有效進行,最後兩個分支也已明確指定。故它自己的有限編碼 是它的有效輸入。
在輸入 上執行 ,它會問 : 在 上會否停機?由於假設 是判定器,這次調用必須回答「是」或「否」。
若 答「是」,其正確性表示 停機;但 的定義卻令這次執行永遠循環。若 答「否」,其正確性表示該次執行不停機;但 會立即接受,因而停機。兩種答案都與 的假設正確性矛盾。
所以這種判定器不存在, 不可判定。上面的識別器依然存在:不可判定是指不存在對所有輸入停機且正確的判定器,不是指不能識別肯定個案。
證明透視
對角線證明在哪裏用到假設
的全域停機性用來保證 的第 2 步一定有答案。若 在 上可以永遠運行,那麼 在 上只是不停機,而這並不矛盾。 的正確性只用在一個配對 上。不顯然的一步是把 自己的編碼交給 ,讓 去預測自己,再令 做出與預測相反的行為。論證之所以封閉,是因為全域停機的 只能給出兩種答案,而每一種都與正確性矛盾。
這裏的自我引用不是要求機器猜測一個不可能的輸出。機器及其輸入都是同一套有效編碼系統中的字串; 把自己已存在的有效編碼當作數據接收。矛盾依賴 在這個配對上既必然停機又正確;移除任何一個保證,便不能原封不動地得到同一結論。
例題 5.2.5
(反駁兩個具體的候選判定器)
取候選 ,它對每個配對都回答「否」,並設 為由它構造的對角機。對有效編碼, 得到「否」並接受,所以 在 上停機,而 卻對配對 回答「否」。再取 ,它對每個配對都回答「是」。由它構造的 對每個有效編碼都永遠循環,特別是在 上,而 卻聲稱它會停機。每個候選都在自己對角機的對角輸入上答錯。邊界情況:對不是有效編碼的字串, 與 都直接拒絕;反駁只用到對角輸入。
反例模式
時間上限不能判定停機
固定正整數 。假設測試模擬 共 步,仍未停止就回答「否」。但一台機器可以先做 步無害工作,然後停機;測試便在這個停機個案上答錯。提高固定上限只會改變反例,不會令方法普遍正確。
歸約:改變輸入,但保留答案
考慮看似更窄的語言:
定義 5.2.6
(多對一歸約)
從語言 到 的多對一歸約,寫作 ,是字串上的全域可計算函數 ,滿足
構造新個案時不能先知道舊個案的答案。若有 的判定器,就先算 ,再運行該判定器並返回它的答案;兩階段都停機,便得到 的判定器。
定理 5.2.7
(空輸入停機問題不可判定)
下面構造的映射 是多對一歸約 。因此 不可判定。
證明
(從任意輸入停機歸約到空輸入停機)
對有效 ,有效構造機器 :忽略它自己的輸入,模擬 在固定字串 上的運行。我們可以機械地把 與 的有限描述嵌入模擬程式,因此程式碼可有效產生。令
若 格式不正確,就輸出一台固定永遠循環機器的編碼。這使 對所有字串有定義,也保持格式錯誤的字串不屬於 這個事實。
在空輸入上, 恰在 於 上停機時停機。因此
所以 。若 有判定器,上述程序便可判定 ,與對角線論證矛盾。故 不可判定。
證明透視
為甚麼歸約映射只負責寫程式碼
映射 只寫出 的程式碼,從不運行 :若構造 需要先知道 在 上會否停機,這個歸約就已經解決了停機問題。 對所有字串有定義,這解釋了格式錯誤的分支:由 構造出的 判定器必須處理每一個字串。等價式的兩個方向都用到: 在 上停機,就是 在空輸入上停機;不停機則仍然不停機。最後,方向至關重要:被轉移到目標 的,是來源 經對角線論證得到的不可判定性。
常見錯誤
(把歸約方向弄反)
箭頭方向很重要:我們把已知不可判定的問題轉成目標問題。只證明 並不能推出 不可判定,因為容易的問題也可能歸約到困難問題。事實上此例也存在反方向歸約,但證明中用到的不是它。
例題 5.2.8
(把歸約應用到具體輸入)
設 在輸入 上停機,在其他每個輸入上都永遠運行。對 ,機器 忽略自己的輸入並模擬 ,所以它在 上停機: 且 。對 , 模擬 並永遠運行,所以 且 。兩個像都由同一個機械的包裝程序產生,不需要運行 。邊界情況:若 不是有效配對, 是固定循環機器的編碼,於是 且 ,等價式對格式錯誤的字串同樣成立。
儘管如此, 是可識別的:給定有效 ,模擬 在 上的運行;若停止便接受。若永遠循環,則沒有否定答案,與 的情況一樣。這並未產生判定器。
練習與解答
快速檢查
(模擬已運行一百萬步仍未停止,這能證明它永遠不停機嗎?)
想一想有限軌跡能排除甚麼、不能排除甚麼。
解答 · 答案
不能。若程式在第一百萬零一步停止,至今的觀察完全相同。有限軌跡可以證明某次運行已停機,但這個觀察本身不能證明它永遠不會停止。
快速檢查
(對角線證明中,若 說 在自己的編碼上停機,會發生甚麼?)
看看 回答「是」時 走哪個分支。
解答 · 答案
的定義令它在 說「是」時永遠循環; 的正確性卻要求同一次執行停機,構成矛盾。回答「否」亦有相反矛盾,因為 會立即接受並停機。
快速檢查
(給定 及 ,描述歸約使用的空輸入機器。構造它時是否要先判定 在 上會否停機?)
寫出包裝程式的程式碼,與運行它是同一回事嗎?
解答 · 答案
產生一個嵌入 及 的包裝機器 ;它忽略自身輸入並模擬 。因此 在 上的行為恰是 的行為。產生程式碼是有限語法操作,不需要把模擬運行到結束,也不需要先判斷它會否停機。
快速檢查
(若問題 可歸約到不可判定問題 ,單憑這點可推出 不可判定嗎?)
想一個明顯可判定的 ,以及它到某個已知不可判定語言的映射。
解答 · 答案
不能。例如,空語言可歸約到任何有可計算固定非成員的語言,但空語言本身可判定。若要用 證明目標 不可判定,要從已知不可判定的 出發,構造可計算歸約 。
不可判定性說的是指定問題不存在對所有輸入都終止的統一程序。對個別程式,我們仍可能給出簡短的停機或不停機證明;不能保證的是對每個編碼程式與輸入都作出正確有限回答。