## 10.6 不可計算的問題 到目前為止，我們討論的所有問題都是可解的。有些問題的解法非常有效，有些問題的 解法則比較復雜。Hanoi 塔之類的問題稱為難解問題，因為當問題規模較大時，相應算法需 要太多太多的時間（或空間）來完成計算，事實上是無效、不可行的解法。 現實中還存在比難解問題更麻煩的問題，那就是不可解問題。考慮這個場景：計算機正在執行一個程序，我們坐在邊上等待程序結束。當過了很久程序還沒結束時，我們該怎么辦 呢？我們可能推測程序中出現了無窮循環，永遠不會結束，這樣我們就必須強行中斷程序運 行甚至重啟計算機。然而，我們并不能絕對肯定是出現了無窮循環，也許是因為計算太復雜 導致時間過長呢？這樣的話，我們就該繼續等待。顯然，這是一個兩難困境。我們設想，要 是有這么一個程序 P 就好了：P 的功能是以另一個程序 Q 的代碼作為輸入，并分析 Q 中是 否包含無窮循環。然而很遺憾，這樣的程序 P 是不存在的！這個問題其實對應于圖靈機的 停機問題，下面對此進行簡要介紹。 圖靈機 英國數學家 Alan Turing 于 1936 年發明了一種抽象機器用于研究計算的本質，人們稱這 種機器為圖靈機（Turing machine）。圖靈機能夠模擬算法式計算，即按預定的規則一步一步 執行基本指令的過程。現代計算機就是這樣按照預定的程序一步一步執行指令的，因此可以 視為圖靈機的具體實現。 人們為了進行計算，需要用到紙和筆。類似地，圖靈機在“硬件”上由一條紙帶和一個 讀寫頭組成：紙帶用于記錄信息，讀寫頭用于讀寫信息。紙帶在讀寫頭下移動，讀寫頭即可 在紙帶上寫下符號（如 0 和 1）或讀出符號。這有點類似磁帶錄音機中磁帶與磁頭的關系， 但與錄音機的順序錄音或回放不同的是，圖靈機的讀寫頭和紙帶受預定的規則（相當于我們 熟悉的程序）的控制。參見圖 10.13。  圖 10.13 圖靈機的紙帶和讀寫頭 下面對圖靈機進行更詳細的描述。一個圖靈機涉及以下一些要素： + 紙帶：紙帶被劃分成一個個格子單元，單元中可以寫入符號。紙帶在向左、向右兩 個方向上都是無限延伸的，即圖靈機的存儲能力不受限制。 + 讀寫頭：用于讀寫紙帶單元中的符號。紙帶在讀寫頭下可以向左或向右移動，每次 移動一個單元。當然也可以理解成紙帶不動而讀寫頭左右移動。 + 符號表：能夠寫入紙帶的合法符號。具體用什么符號系統并不重要，正如現代計算 機基于二進制一樣，只要提供 0 和 1 兩個符號就足夠從事任何計算。 + 狀態：圖靈機在任一時刻都處于某種狀態，例如當前讀寫頭下方是 0 或 1 即對應不 同狀態。不同狀態的數目是有限的。兩個特殊狀態分別是開始狀態和停止狀態。 + 指令：指令描述的是如何根據圖靈機的當前狀態以及當前讀寫頭所讀到的符號來控 制圖靈機執行特定動作并轉換為新的狀態。形如： 當前狀態，輸入符號 ? 新狀態，輸出符號，移動讀寫頭 預定的多條指令構成一個指令表（程序），它完全決定了圖靈機的行為。圖靈機的 運行就是按照指令表所確定的狀態轉換規則一步一步進行狀態轉換的過程。 下面我們設計一個對給定正整數 n 加 1 的圖靈機。 【圖靈機 T+1】T+1 的符號表僅由 0（表示空白）和 1 組成。正整數 n 在紙帶上用 n 個連續單 元的 1 表示，例如 1、2、3 在紙帶上分別表示為 1、11、111。讀寫頭初始位置是在輸入數 據 n 的左方，停止位置是在輸出數據 n+1 的最后一位 1 之上。初始狀態為 s1，停止狀態為 s3。指令表如下： ``` s1, 0 => s1, 0, R s1, 1 => s2, 1, R s2, 0 => s3, 1, Stop s2, 1 => s2, 1, R ``` 假設輸入數據是 3，則圖 10.14 展示了 3+1 的計算過程。讀寫頭里記錄的是圖靈機當前 狀態。  圖 10.14 計算 n+1 的圖靈機 T+1（輸入 n=3） 第 1 條指令的意義是：當圖靈機 T+1 處于 s1 狀態，并且讀寫頭所讀單元的內容是 0，那 么就保持 s1 狀態，也不改動該單元的內容，然后讀寫頭右移。第 3 條指令的意義是：當 T+1 處于 s2 狀態，并且讀寫頭所讀單元里的內容是 0，那么就進入 s3 狀態，將該單元內容改為 1， 然后停止。其他兩條指令的意義請讀者自行解讀。從初始狀態開始執行這些指令，經過 6 步狀態轉換，T+1 將終止，并且終止時紙帶上的計算結果是 4 個連續的 1，表示正整數 4。 盡管圖靈機是如此簡單，但它的計算能力卻非常強大。從上例可知，存在計算 n+1 的圖靈機，由此不難想象可以設計出計算 n+m 的圖靈機，進而可以設計出計算 n×m 的圖靈 機，等等。注意，這里我們談論圖靈機的計算能力，并非針對它的計算速度或存儲空間，因 為圖靈機畢竟不是現實的計算機。研究圖靈機是為了在理論上探索計算的能力和局限，例如 回答計算機科學的一個根本問題：究竟什么是可計算的？對此，Turing 和 Church 分別通過 研究圖靈機和λ演算，得出了一個重要假設——Turing-Church 論題，其大致意思是：一個 問題是能行可計算的（即算法可計算），當且僅當該問題能用圖靈機來計算。因此，圖靈機 事實上給出了“算法計算”或“機械計算”的精確意義。 圖靈機的強大計算能力有一個重要表現，那就是一個圖靈機可以模擬另一個圖靈機的工 作。如果將圖靈機 T 1 的功能進行編碼，然后輸入給另一圖靈機 T 2，那么 T 2 就能表現得像 T 1 一樣。打個比方，這就像一個人可以模擬另一個人的行為一樣。假設張三既懂加法又懂 乘法，并且他知道不懂乘法的李四總是錯誤地將 n×m 算成 n+m，那么當我們將 n 和 m 輸 入給張三要他計算 n×m 時，他完全可以故意輸出 n+m 來冒充李四。 既然一個圖靈機可以模擬另一個圖靈機的行為，那我們就可以設計一個通用圖靈機，它 可以模擬任何圖靈機的行為。對此讀者應不陌生，因為我們在第 1 章就說過，現代計算機是通用計算機，給它安裝不同的程序，就能完成不同的功能。圖 10.15 展示了如何用通用圖靈 機 UT 來模擬某個特定圖靈機 T：將 T 的行為（指令表）用 0/1 序列進行編碼得到 Tcode， 連同 T 的輸入數據 data 一同輸入給 UT，然后 UT 即可對 Tcode 進行解碼，并針對 data 來模 擬 T 的行為。  圖 10.15 通用圖靈機 UT 模擬特定圖靈機 T 如果用函數來表示圖靈機，則 UT 模擬 T 的行為可表示為 ``` UT(Tcode,data) = T(data) ``` 停機問題 對任何給定的圖靈機 T，以及輸入數據 data，T 可能停機，也可能不停機。上面計算 n+1 的圖靈機 T+1 顯然總是能停下來的，因為正整數 n 在紙帶上表示為 n 個連續的 1，T+1 的第二 條指令要求讀寫頭只要讀到 1 就不斷向右移，因此最終會讀完這有限個數的 1，并讀到連續 1 右方的第一個 0，第三條指令會將這個 0 改寫為 1，并停機。 一個圖靈機也很容易不停機。例如這樣一條指令就有可能令圖靈機無法終止： ``` s1, 0 => s1, 0, NoMove ``` 即，在 s1 狀態讀到 0 時，保持 s1 狀態和單元內容 0 不變，并且讀寫頭也不移動。如果一個 圖靈機進入到 s1 狀態并且恰好讀到 0，那么這個圖靈機就將永遠處于這個狀態而不停機。不難看出，這條指令的行為與 Python 中的無窮循環語句 ``` while True: pass ``` 是一樣的。順便說明一下，pass 是 Python 語言的一條語句，功能是什么都不做。 我們當然希望設計的圖靈機能正確地完成計算并停機，可現實經常不能如我們所愿，就 像我們編寫的程序經常陷入無窮循環而不能終止一樣。更讓人煩惱的是，當圖靈機（或程序） 一直在執行而不終止時，我們并不知道它是否陷入無窮循環了！現實中，我們只能通過運行 時間長短的經驗來判斷到底是什么情況，但這畢竟是不可靠的。有沒有辦法來檢驗圖靈機是 否停機呢？也就是說，能不能設計這樣的通用圖靈機 HT，它的輸入是另一個圖靈機 T（的 編碼）和 T 的輸入 data，它的功能是判斷 T 在 data 上執行后是否停機：如果是，則 HT 輸出 1 并停機；如果不是，則 HT 輸出 0 并停機。亦即，HT 是判斷其他任意圖靈機是否終止的 圖靈機。 上述 HT 是否存在？這就是所謂停機問題（Halting problem）。Turing 的一個重要成果就 是證明了 HT 不存在！下面我們用程序設計的術語來非形式地描述這個證明。 從程序設計角度看，停機問題就是要編一個程序 halt，它讀入另一個程序 prog 的源代 碼，并判斷 prog 是否導致無窮循環。由于 prog 的行為不僅依賴于它的源代碼，還依賴于它 的輸入數據，因此為了分析 prog 的終止性，還要將 prog 的輸入數據 data 交給 halt。由此可 得 halt 的規格說明： ``` 程序：停機分析程序 halt； 輸入：程序 prog 的源代碼，以及 prog 的輸入數據 data； 輸出：如果 prog 在 data 上的執行能終止，則輸出 True，否則輸出 False。 ``` 讀者也許會覺得向程序 halt 輸入另一個程序 prog 作為處理對象有點不可思議，但其實 這是非常普通的事情。例如，編譯器（或解釋器）就是這樣的程序：將一個程序 P 的源代 碼輸入給編譯器程序 C，C 可以分析 P 中是否有語法錯誤，有則報錯，沒有則輸出 P 的目標 代碼。 在停機問題中，正常情況下是想運行 prog(data)，但又不知道這個執行過程能不能終止， 于是希望將 prog 的代碼和 data 交給停機分析程序 halt，由 halt 來判斷 prog(data)的終止性。 由 halt 的程序規格可見，halt 總是能得出結論并終止的，從而避免了直接執行 prog(data)時 無法確切知道它是否能終止的困擾。 設計 halt 程序的初衷可以理解，可惜這個程序是編不出來的。我們用反證法來證明這個 結論，即先假設存在程序 halt，然后推導出矛盾來。 假如我們已經設計出了停機分析程序 halt，其參數是兩個字符串：prog 是被分析的程序 的源代碼，data 是 prog 的輸入數據。 ``` def halt(prog,data): …… # 分析 prog 代碼，如果對 prog 輸入 data 時運行能終止 return True …… # 如果 prog 運行在 data 上不能終止 return False ``` 利用 halt 的功能，我們可以編出如下這個奇妙的程序： ``` def strange(p): result = halt(p,p) if result == True: # 即 p(p)終止 while True: pass else: # 即 p(p)不終止 return ``` 運行 strange(strange),結果如何? 函數 strange()有一個字符串類型的形參 p，調用時需傳遞一個程序給它，不妨假設所傳 遞的程序也是以一個字符串數據作為輸入。strange 首先調用 halt(p,p)，這里的關鍵技巧是， 傳遞給函數 halt 的形參 prog 和 data 的實參都是 p，亦即我們要分析程序 p 以它自己為輸入 數據時——即 p(p)——運行是否終止。strange 根據 halt(p,p)的分析結果來決定自己接下去怎 么做：如果結果為 True，即 p(p)能終止，則 strange 進入一個無窮循環；如果結果為 False， 即 p(p)不終止，則 strange 就結束。 strange 程序看上去有點費解，但只要 halt 存在，strange 在編程方面顯然沒有任何問題。 接下來是證明過程的最美妙的部分：假如將 strange 自身的源代碼輸入給 strange 時會發生什 么？更確切地，strange(strange)能否終止？ 我們參照上面的 strange 代碼來分析。假如調用 strange(strange)不終止，那必然是因為 執行到了代碼中條件語句的 if result == True 部分，即 halt(strange,strange)返回了 True，這又 意味著 strange 以 strange 為輸入時運行能終止！另一方面，假如調用 strange(strange)能終止， 那必然是因為執行到了條件語句的 else 部分，即 halt(strange,strange)返回了 False，這又意味 著 strange 以 strange 為輸入時運行不能終止！總之，我們得到了如下結論： 若 strange(strange)不終止，則 strange(strange)終止； 若 strange(strange)終止，則 strange(strange)不終止。 這樣的結論在邏輯上顯然是荒謬的。導致這個矛盾的原因在于我們假設了 halt 的存在，并利 用了 halt 的功能。至此，我們證明了編寫 halt 程序是不可能完成的任務，即停機問題是一個 不可解問題。 停機問題不可解的證明過程具有非常深刻的意義，它告訴我們算法式計算具有本質上的 局限性。計算機雖然在各行各業解決了很多問題，但是確實存在計算機不能解決的問題。