艾倫·圖靈在1936年邁出了關鍵一步，證明不完備性是自然且普遍存在的，他論證了不存在通用的程式來判斷一個獨立的計算機程式是否會最終停止執行。
為了證明這個結論，我們假設我們想要證明的結論的反面是成立的。 也就是說，假設存在一個通用程式 H，它可以判斷任何給定的計算機程式是否會停止執行。 從這個假設出發，我們將推匯出矛盾。 這就是所謂的歸謬法證明。
因此，假設存在 H，我們可以構建以下程式 P，它使用 H 作為子程式。 程式 P 知道自身的大小（以位元為單位，N）——P 中肯定有空間容納數字 N——然後使用 P 包含的 H，P 會檢查所有大小不超過 N 位元 100 倍的程式，以檢視哪些程式會停止執行，哪些不會。 然後 P 執行所有停止執行的程式，以確定它們產生的輸出。 這將精確地是複雜性不超過 N 位元 100 倍的所有數字物件的集合。 最後，我們的程式 P 輸出不在此集合中的最小正整數，然後 P 自身停止執行。
關於支援科學新聞
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道 訂閱。 透過購買訂閱，您正在幫助確保未來能夠繼續講述關於塑造我們當今世界的發現和想法的具有影響力的故事。
因此，P 停止執行，P 的大小為 N 位元，並且 P 的輸出是一個整數，該整數無法由大小小於或等於 N 位元 100 倍的程式生成。 但是 P 剛剛將此整數作為其輸出生成，並且它太小而無法做到這一點，因為 P 的大小僅為 N 位元，遠小於 N 位元 100 倍。 矛盾！ 因此，用於判斷程式是否會停止執行的通用程式 H 不可能存在，因為如果存在，那麼我們實際上可以使用 H 構建這個自相矛盾的程式 P。
最後，圖靈指出，如果存在一種萬物理論，它總是能夠讓你證明一個單獨的程式會停止執行，或者證明它永遠不會停止執行（無論哪種情況屬實），那麼透過系統地執行所有可能的證明，你最終可以判斷個別程式是否會停止執行。 換句話說，我們可以使用這個理論來構建 H，而我們剛剛證明 H 不可能存在。 因此，對於停機問題，不存在萬物理論。
類似的推理表明，對於所有長度不超過 N 位元的程式，沒有哪個長度明顯短於 N 位元的程式可以解決圖靈停機問題。