
停止問題不可判定 -- 以 C 語言實證
圖靈與停止問題誕生於一百年前 (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% 正確的」這個概念,而這也是「圖靈」透過「停止問題」所傳達出來的概念,那就是「電腦的能力是有極限的」! 參考文獻
|
Kuan-Yi Lee
01/22
已經忘了Halting Problem是什麼了,一不小心就認真的看了好久,然後總覺得哪裡怪怪的
文章中的命題是這樣的:
請問您是否有辦法寫一個程式,判斷另一個程式會不會停,如果會停就輸出 1,不會停就輸出 0。
Wiki中文的說明是這樣的:
停機問題就是判斷任意一個程序是否會在有限的時間之內結束運行的問題。
Wiki英文的說明是這樣的:
Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever.
命題應該要加個『任意』兩個字的,有沒有這兩個字感覺差很多...