梅爾文·亨裡克森——哈維·瑪德學院榮譽數學教授——對此進行了解釋
庫爾特·哥德爾因1931年發表他的不完備性定理而聞名。 |
對於幾乎所有不是數理邏輯專家的讀者來說，用數學上精確的語言陳述哥德爾不完備性定理只會掩蓋其重要的直觀內容。因此，我將用計算機語言重新措辭並簡化它。
關於支援科學新聞報道
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道： 訂閱。透過購買訂閱，您正在幫助確保未來能夠繼續釋出關於塑造我們今天世界的發現和想法的有影響力的報道。
想象一下，我們可以訪問一臺非常強大的計算機，名為 Oracle。與我們熟悉的計算機一樣，Oracle 要求使用者“輸入”遵循精確規則的指令，並以同樣遵循這些規則的方式提供“輸出”或答案。相同的輸入將始終產生相同的輸出。輸入和輸出都寫成整數（或自然數），Oracle 只執行通常的加法、減法、乘法和除法運算（如果可能）。與普通計算機不同，無需擔心效率或時間。Oracle 將執行正確給出的指令，無論需要多長時間，並且只有在指令執行完畢後才會停止——即使需要超過一百萬年。
讓我們考慮一個簡單的例子。記住，如果一個大於 1 的正整數（我們稱之為 N）除了 1 和 N 之外不能被任何正整數整除，則稱為素數。您將如何要求 Oracle 判斷 N 是否為素數？告訴它將 N 除以 1 到 N-1 之間的每個整數，並在除法結果為整數或達到 N-1 時停止。（實際上，如果達到 N 的平方根，您可以停止。如果在該點之前 N 沒有被任何數整除，則 N 是素數。）
哥德爾定理所說的是，存在一些僅涉及整數算術的、正確提出的問題，Oracle 無法回答。換句話說，有些陳述——儘管輸入正確——Oracle 無法評估以判斷它們是真還是假。這樣的斷言被稱為不可判定的，並且非常複雜。如果您將其中一個問題帶給哥德爾博士，他會向您解釋，這樣的斷言將永遠存在。
即使您獲得了一個“改進”的 Oracle 模型，稱之為 OracleT，其中一個特定的不可判定語句 UD 被判定為真，也會生成另一個不可判定語句來取代它。更令人困惑的是，您也可能獲得另一個“改進”的 Oracle 模型，稱之為 OracleF，其中 UD 會被判定為假。無論如何，這個模型也會生成其他不可判定語句，並且可能會產生與 OracleT 不同的結果，但同樣有效。
您是否覺得這令人震驚且接近悖論？當哥德爾在 1931 年公佈他的不完備性定理時，數學界更加震驚。哥德爾沒有用計算機語言表達他的結果。他是在一個確定的邏輯系統中工作的，數學家們希望他的結果取決於該系統的特殊性。但在接下來的十年左右，包括斯蒂芬·C·克萊恩、埃米爾·波斯特、J.B.羅瑟和艾倫·圖靈在內的許多數學家證明並非如此。
對這項偉大定理的後果的研究一直持續到今天。任何可以使用網際網路並透過 Alta Vista 等搜尋引擎訪問資訊的人都可以找到數百篇關於哥德爾定理的文章，質量參差不齊。不過，最值得閱讀的書籍之一是歐內斯特·內格爾和詹姆斯·R·紐曼合著的《哥德爾證明》，該書於 1958 年出版，並於 1983 年由紐約大學出版社發行平裝本。