圖靈停機問題

計算機中美妙而神奇的程式解決了人類生活中的各種問題：

搜尋引擎可以從數以千億的網頁中檢索到我們需要的內容，深度學習模型可以在圍棋、星際爭霸等複雜遊戲中戰勝經驗豐富的人類。甚至只要時間足夠，程式能解決旅行商最短路徑、最大完全子圖等複雜問題，似乎程式無所不能。

那麼有沒有程式不能完成的事情呢？

答案是有的，這就是圖靈早在1936年提出的圖靈停機問題

圖靈停機問題產生的現實背景在於，當時的計算機執行程式時，外界無法觀察當前的執行狀態，特別大型程式在執行的時候，研究人員無法判斷程式是正常執行中還是由於 bug 陷入死迴圈。因此如果我們能在執行程式 P 前先執行另一個有限時間結束的程式 Q 對 P 進行判斷，那麼我們就可以提前修改 bug 或者放心的讓 P 進行運算。

圖靈停機問題可以簡單描述為：判斷程式 P 在給定輸入 I 的情況下，能否在有限時間內執行完成？

可惜的是，我們可以從理論上證明，滿足要求的程式 Q 並不存在。

首先我們要理解一個前提：程式本身也作為資料存計算機中，因而可以作為資料成為程式的輸入，即 P（P） 合法。

證明如下

假設存在符合要求的程式 Q，對於任意程式 P 和特定輸入 I，當 P（I） 能在有限時間停止時，Q（P， I） 返回 true，當 P（I） 陷入死迴圈時，Q（P， I） 返回 false，則 Q（P， P） 判斷 P（P） 能否停機。

程式 Q 的虛擬碼如下：

bool Q（P， I）：

{

if （P（I） 能在有限時間停機）{

return true；

}else{

return false；

}

}

現在巧妙地構造一個新的程式 U 可以引出矛盾，程式 U 的虛擬碼如下：

void U（P）：

{

if （Q（P，P） == false）{ // 如果 P（P） 死迴圈

return； // 此時 U 能停機

}else{ // 如果 P（P） 能停機

while（true）{} // 此時 U 會死迴圈

}

}

可以看出，程式 U 的輸入為程式 P（同時也是資料 P）。當 Q 判斷 程式 P 以 P 為輸入會出現死迴圈時，則立刻返回，此時 U 在有限時間內停機。而當 Q 判斷 程式 P 以 P 為輸入能停機時，進入一個死迴圈分支，此時 U 不能停機。同樣，由於程式 U 也可以視為資料，則 U（U） 也是合法的。

那麼問題來了，Q（U， U） 應該返回什麼結果？

讓我們根據定義梳理一下，Q（U， U） 判斷程式 U 在輸入為 U 的情況下能否停機，能停機則返回true，死迴圈則返回false。而 U（U） 能否停機取決於 Q（U， U） 的返回值，當 Q（U， U） 返回false時，U（U） 能停機，否則 U（U） 不能停機。

所以假設 Q（U， U） 返回 false，表示 U（U） 不能停機，但真實的 U（U） 執行起來能停機，推出矛盾；而當假設 Q（U， U） 返回 true，表示 U（U） 能停機，但真實的 U（U） 執行起來不能停機，也推出矛盾。因此前提假設不成立，存在符合要求的程式 Q 並不存在。

這一巧妙的構造其實並不罕見，其矛盾出現的本質在於一個程式可以作為自己的輸入，這一概念可以抽象為“自指”。正如題圖（莫里茨·科內利斯·埃舍爾的《畫手》）中描繪的那樣，兩隻手互相畫出了彼此，以至於存在的悖論。

一旦我們的研究物件出現了自指的可能，那麼會引發諸多悖論，比如理髮師悖論，即一個小島上有一名理髮師，他宣佈自己給且僅給島上所有不給自己理髮的人理髮。那麼如果理髮師不給自己理髮，他就屬於不給自己理髮的人，從而應該給自己理髮；如果理髮師給自己理髮，他就不屬於不給自己理髮的人，從而不應該給自己理髮。理髮師悖論是羅素悖論的形象化表示，羅素悖論給嚴謹的集合論基礎找出了致命的漏洞，引發了第三次數學危機。

為了解決這一危機，1920年代，德國數學家大衛‧希爾伯特提出一個數學計劃史稱“希爾伯特計劃”。這個計劃的主要目標，是為全部的數學提供一個安全的理論基礎，這一理論基礎包含形式化、完備性、相容性、保守性、確定性。希望透過這一理論基礎解決第三次數學危機。

遺憾的是，這一偉大構想不可能成為現實。哥德爾在1931年提出了哥德爾不完備定理，證明一個包含皮亞諾算術公理（簡單理解為自然數及相關運算）的公理化體系，它就不能同時滿足相容性與完備性，其中相容性是指這一公理化體系中的邏輯推理不會自相矛盾，即不存在命題和對應的否命題同時成立，也可稱為邏輯自洽；完備性指該體系中的任意命題，均可證明該命題的真偽，即不存在命題，無法證明成立或者不成立。

哥德爾不完備定理的證明過程同樣用到了自指的概念，透過自然數對映關係，將證明過程與證明命題完成自指的構造，推匯出不可證明命題的存在性。具體細節會在後續文章中介紹。

由於這種涉及自指帶來的悖論或者不完備性，所以也有人悲觀的提出，人類永遠無法創造出和人類一樣的強人工智慧，但這一想法很難得到證明。我期望著我們能創造出強智慧體，這將是人類最接近神的時刻。