圖靈與停止問題

誕生於一百年前 (1912 年) 的圖靈 (Alan Turing)，雖然活著的時候並不是非常受世人注目，但是在死後卻成了電腦領域的傳奇人物，他的人生就像梵谷一樣，以悲劇收場，但是卻留下無限的寶藏。

圖靈在「電腦與數學」上有非常重要的貢獻，如下所示：

1. 1936年「圖靈」在論文 「On Computable Numbers, with an Application to the Entscheidungsproblem」 提出了圖靈機 (Turing Machine) 的概念，並用圖靈機證明了「停止問題」是不可判定的。這件事情正是本文所想探討的主題。

2. 1938年「圖靈」再度提出了「預言機」 (Oracle machine, 神諭機) ，這導致後來 NP-Complete 在 1972 年被 Leonid Levin 與 Cook 提出來，於是 「P = NP?」 這個問題就成了資訊科學領域最受注目的難題之一，直到現在都沒有人可以有效解答。

3. 1940年「圖靈」在「英國密碼破譯中心 – 布萊契莊園」參與了破譯德軍密碼機 Enigma machine 的任務，並接續三位波蘭學者的研究之後提出了 Crib 方法，破譯了德軍的 Enigma 密碼機。

4. 1949年「圖靈」再度提出「圖靈測試」（Turing test）這個概念，這是一種利用「交談方式」測試電腦是否有辦法成功欺騙過人，讓人以為對方是個人而不是電腦的「操作型方法」。這個測試可以用來當作電腦是否有智慧的判斷準則之一。

5. 1952 年，他用自己的大腦寫了一個西洋棋程式，可惜當時電腦技術不夠成熟，後來電腦技術較成熟後該程式就被實作出來了。

6. 1952 年之後他一直在研究「生物型態發生學」，像是「碎型幾何」的數學基礎，因此在生物領域也有相當程度的貢獻。

7. 1952 年，他因「同性戀友人偷竊他的東西而報警」，結果反而被控「明顯的猥褻和性顛倒行為」之罪行，1954 年、他吃了一顆浸過氰化物的蘋果而死了，根據研判很可能是自殺！

在歷史上、很多優秀人物的下場，其實都是無比悽慘的，圖靈就是其中之一。

在本文中，我們會將焦點集中在「停止問題」 (Halting Problem) 上！

雖然停止問題已經是很多資訊科系的人在「計算理論、離散數學」等課程中讀過的問題，但是、您有真的將停止問題寫成程式過嗎？

本文將採用 C 語言實作停止問題的架構，並說明為何停止問題不可解。

但是在討論停止問題之前，先讓我們來看看一個更簡單的問題，那就是羅素提出的「理髮師悖論」，這是理解停止問題的前哨站。

理髮師悖論

理髮師悖論可以描述如下：

在某一個小世界裏，有一個理髮師，他宣稱要為該世界中所有不自己理頭髮的人理髮，
但是不為任何一個自己理頭髮的人理髮！

請問、他做得到嗎？

您覺得呢？

這個問題的答案是，他絕對做不到，原因出在他自己身上：

如果他「為」自己理頭髮，那麼他就為「一個自己理頭髮的人理髮，違反了後面的宣言。

如果他「不為」自己理頭髮，那麼他就沒有為「該世界中 "所有" 不自己理頭髮的人理髮」，
因此違反了前面的宣言。

於是、他理也不是、不理也不是，這就像中國傳說故事裏「矛與盾」的故事一樣，
他的問題陷入兩難，產生「矛盾」了。

所以、該理髮師想做的事情是不可能做得到的！

停止問題

同樣的，「停止問題」也是一個無法用電腦寫程式做到的問題，讓我們先來看看停止問題的描述。

停止問題：

請問您是否有辦法寫一個程式，判斷另一個程式會不會停，
如果會停就輸出 1，不會停就輸出 0。

這個問題看起來好像很容易，但事實上卻很難。而且圖靈證明了「停止問題」是無法用電腦 (圖靈機) 正確判定的。

由於圖靈的證明是建構在圖靈機上的，而圖靈機又很難用幾句話簡單描述，因此我們改用「現代程式」的方法證明停止問題，證明過程如下：

停止問題採用教數學的方式來說，是我們想定義一個函數 isHalt(code, data) ，
該函數可以判斷程式 code 在輸入 data 之後，是否會停止，
也就是 code(data) 會不會停止。

如我用程式寫下來，可寫成如下的演算法：

isHalt(code, data) = 1  假如 code(data) 會停就輸出 1
                   = 0  假如 code(data) 不停就輸出 0 

但是、假如上述函數真的存在，那麼我們就可以寫出下列這個函數：

function U(code) // 故意用來為難 isHalt(code, data) 的函數。
  if (isHalt(code, code)==1) // 如果 isHalt(U, U)=1，代表判斷會停
    loop forever //   那 U 就進入無窮迴圈不停了，所以 isHalt(U,U) 判斷錯誤了。
  else           // 如果 isHalt(U, U)=0，代表判斷不停
    halt         //   那 U 就立刻停止，所以 isHalt(U,U) 又判斷錯誤了。
end

如此、請問 isHalt(U,U) 應該是甚麼呢？ 這可以分成兩種情況探討：

1. 假如 isHalt(U, U) 傳回 1，那麼就會進入無窮回圈 loop forever，
   也就是 U(U) 不會停 

=> 但是 isHalt(U,U)=1 代表 isHalt 判斷 U(U) 是會停的啊？
   於是 isHalt(U, U) 判斷錯誤了。

2. 假如 isHalt(U, U) 傳回 0，那麼就會進入 else 區塊的 halt，
   也就是 U(U) 會立刻停止

=> 但是 isHalt(U,U)=0 代表 isHalt 判斷 U(U) 是不會停的啊？
   於是 isHalt(U, U) 又判斷錯誤了。

於是、我們證明了停止問題是不可能做到 100% 正確的，
因為 isHalt 永遠對 U(U) 做了錯誤的判斷。

以 C 語言實作停止問題

現在、我們可以用 C 語言來實證上面的停止問題了，以下是我們的程式碼：

檔案: halting.c

#include <stdio.h>

// 您不可能寫出一個 isHalt 函數，正確的判斷 code(data) 會不會停。
// 因為、isHalt(U, U) 永遠都會判斷錯誤，原因如下述：
//   如果您用 HALT=0，會輸出 isHalt(U, U)=0，然後就停了；這代表判斷不停，結果卻停了。
//   如果您用 HALT=1，會輸出 isHalt(U, U)=1，然後就當了；這代表判斷會停，結果卻沒停。
//   如果您用更複雜的方式，U(U) 的行為永遠與 isHalt(U, U) 的回答相反，因此總是無法正確判定。
// 不相信的話，請您任意修改下列的 isHalt 函數試試看！

int isHalt(void *code, void *data) {
   return HALT; 
}

// U 函數就是故意創造來讓 isHalt 函數無法正確決定的一個函數。
int U(void *code) {
  if (isHalt(code, code)) // 如果 isHalt(U, U)=1，代表判斷會停
    while (1);            //   那 U 就進入無窮迴圈，也就是 U 不會停，所以isHalt(U,U)判斷錯誤了。
  else                    // 如果 isHalt(U, U)=0，代表判斷不停
    exit(1);              //   那 U 就立刻停止，所以 isHalt(U,U) 又判斷錯誤了。
}

int main() {
  printf("isHalt(U, U)=%d\n", isHalt(U, U)); // isHalt(U, U) 的輸出結果
  U(U);                                      // 總是與 U(U) 的行為相反的
  // 也就是 isHalt(U, U)無法辦法正確判斷 U(U) 的停止行為，
  // 於是證明了停止問題是無法用電腦解決的。
}

執行結果：

D:\Dropbox\Public\web\codedata\code\halting>gcc -DHALT=0 halting.c -o halting

D:\Dropbox\Public\web\codedata\code\halting>halting
isHalt(U, U)=0

D:\Dropbox\Public\web\codedata\code\halting>gcc -DHALT=1 halting.c -o halting

D:\Dropbox\Public\web\codedata\code\halting>halting
isHalt(U, U)=1
然後就當機了，必須按 Ctrl-C 才能強制中止 .....

雖然在上述程式中，我們的 isHalting(code, data) 函數寫得很簡單，單純只是用 `return HALT` 傳回 HALT 這個 define 的定義值而已，但是不管 HALT=1 或 HALT=0，isHalt(U, U) 都會判斷錯誤。

當 HALT=1 時，會輸出 isHalt(U, U)=0 ，代表 isHalt 判斷 U(U) 不會停，
  結果執行 U(U) 時程式執行到 exit(1) 這個指令就停了。

當 HALT=0 時，會輸出 isHalt(U, U)=1 ，代表 isHalt 判斷 U(U) 會停，
  結果執行 U(U) 時卻是當機了，也就是 U(U) 事實上不會停。

因此、不論哪種情況，isHalt(U, U) 都會做錯誤的判定。

讀者可以試著修改 isHalt 函數，想辦法讓他能夠在 isHalt(U,U) 上輸出與 U(U) 行為一致的結果，看看您是否做得到。

當然、如果您引入某些「狀態、亂數、或者是用程式修改自身的程式碼」，或許會造成一些讓 isHalt(U,U) 的輸出與行為一致的結果，(例如在 isHalt 函數內檢視堆疊，看看是否在 U 函數內被呼叫過，若是的話就盡型特殊處理 ….)，但這些「奇技淫巧」並無法「讓停止問題變成可以判定」，只是讓該程式的輸出與執行結果有可能一致而已。

結語

在本文中，我們用 C 語言實證了停止問題的慨念，以便讓抽象的「計算理論」能夠落實為程式，希望透過這種方式，能讓各為「程式人」更瞭解「電腦有些事情是永遠都無法做到 100% 正確的」這個概念，而這也是「圖靈」透過「停止問題」所傳達出來的概念，那就是「電腦的能力是有極限的」！

參考文獻

1. 維基百科：停機問題
2. 維基百科：理髮師悖論
3. 維基百科：哥德爾不完備定理
4. 維基百科：艾倫·圖靈
5. 維基百科：NP完全