遞迴定理（recursion theorem）

有件事聽起來不可能：一個會印出自己原始碼的程式，或更一般地，一台能取得自己完整描述、再拿它去計算的機器。你可能反駁說這需要無限套疊，程式碼裡包含程式碼、裡頭又包含程式碼。遞迴定理說：不需要無限退行；這種自指永遠可達成。任何你能描述、把「我自己的描述」當作給定輸入來用的計算，事實上都能被造出來。

謹慎地敘述：對任何取兩個輸入（自己的假想描述與一個一般輸入）的圖靈機 T，存在一台機器 R，使得 R 在輸入 w 上的行為，恰如 T 在 (R 的描述, w) 上執行。換句話說，R 可以表現得彷彿自己的原始碼被免費遞給了它。這個構造是一個乾淨的把戲：你造一個部件去產生整體的描述，用一招「先計算、再組合」（與 quine 如何印出自己密切相關），使機器從內部重建自己的文本而不陷入循環退行。定理保證這個不動點存在；你不必靠魔法去找到它。

遞迴定理在兩方面要緊。其一，它是通往不可判定性的俐落替代路徑。要不靠對角線論證證明 A_TM 不可判定，先假設 A_TM 的判定器 H 存在；建造一台機器 R，它取得自己的描述、問 H「R 是否接受它的輸入」，然後做與 H 裁定相反的事。R 如今在自己的行為上與 H 矛盾，所以 H 不可能存在。這是把說謊者悖論做成程式：「這句話是假的」變成「這台機器當且僅當它不接受時才接受」。其二，它是關於自指的深刻、真正令人驚奇的陳述，形式化了計算的自我複製（quine 背後、以及類比地、自我複製程式背後的原理），並支撐起橫跨邏輯的諸多結果，包括哥德爾不完備定理——那正是同一招自指放進算術裡。