那份顧慮：程式真能說出自己的名字嗎？
在這一整階裡，歸約一直是個翻譯器：把一個已知不可判定的問題，以正確的方向翻成你的問題，你的問題便繼承了那份難度。我們建的第一個翻譯器——針對接受問題 A_TM的那個——倚賴了一個你大概仍覺得有點不自在的動作：一台把自己的描述當輸入的機器。你在不可判定性那一階遇到的對角線機器，字面上就是拿一台停機檢查器去問它自己。這聞起來像條咬住自己尾巴的蛇。本篇償還這筆債：證明這個動作是健全的，並給它一個名字。
首先，為何這份顧慮是正當的？當你寫一台圖靈機——也就是你那本可讀、可擦、可重寫的無盡筆記本——它的轉移表在運行之前就已固定。這台機器並非一出生就握著一份自己的印本。要它「讀自己的程式碼」，聽起來像要一本書在第一章裡裝進一份與該書同樣大小、完整無缺的副本，而那會無止盡地遞迴下去。自然的猜測是：自我指涉必須被禁止，就像一個誠實的定義不能用同一個詞去定義那個詞。
令人驚訝之處——而第一次遇到時，它確實令人驚訝——在於這個猜測是錯的。存在一個徹底有限、機械化的把戲，讓任何程式都能算出自己完整的描述，然後拿那個字串去做任何它想做的事。沒有無窮回退，也沒有魔法。保證這件事的結果就是遞迴定理（recursion theorem），一旦你掌握了它，計算中的自我指涉便不再是一個令人害怕的悖論，而成為一件你會主動去拿的工具。
Quine：親手造一個會印出自己的程式
在進入定理之前，先用最小的情形把直覺建起來：一個會印出自己的原始碼、別的什麼都不印、且不吃任何輸入的程式。這樣的程式稱為 quine（自我複製程式）。它讓人覺得不可能，理由相同——要印出自己，它就得包含自己——然而 quine 在每一種真實語言裡都存在。化解這個回退的把戲，是把程式拆成兩部分：一塊描述程式碼的資料，加上一段知道如何把資料、以及「由資料重建出的自己」一起印出來的程式碼。
看著那個回退斷掉。資料不需要包含一份自己——它只描述程式碼那一半。程式碼那一半接著做兩次列印：印出程式碼（它能從資料取得），再印出資料（加上正確的引號，好讓它出來時又是一份資料）。每一半描述的是另一半，所以兩者都不必包含自己，整體於是收攏成某個有限的東西。這個唯一的點子——描述那個「不是你自己」的部分，再從描述重建出你自己——就是全部的祕密，而它能原封不動地放大到圖靈機上。
PART A (the CODE): a machine that reads PART B off its own input, builds a machine whose description is exactly B followed by a printout of A reconstructed from B, then prints that whole thing. PART B (the DATA): a literal, quoted copy of PART A's text. Run A on B: step 1 print A (A knows its own text because B spells it out) step 2 print B (with quoting, so it prints as data, not as code) Output = A followed by B = the original program. It printed itself.
遞迴定理，平實地陳述
把定理用一句誠實的話說出來。假設你能寫一台機器 T，它吃兩個輸入——某台機器的描述（叫它 w）與一個普通輸入 x——並計算你想要的任何東西。那麼你就能自動建出單一的一台機器 R，使得 R 在輸入 x 上的行為，恰恰等同於「把 T 的第一個輸入 w 換成R 自己的描述」時 T 的行為。用程式話講：你可以在程式裡任何地方寫下「我自己的原始碼」這個詞，並把它當成一個已經算好的字串，免費取用。產出 R 的那個構造是有限且機械化的；它把 quine 把戲（描述另一半、重建自己）一般化，於是你永遠不必重新發明它。
仔細看清它是什麼、不是什麼。它不是說一台有限機器偷偷存了一份無限巢狀的自己——那才真的不可能。它是說一台機器能按需算出自己的描述，正如 quine 是產生它的文本、而非預先展開地包含它。而且它並不奇異：每一個圖靈完備的系統都具備它，這正是為何所有圖靈完備的語言都允許 quine 與自我指涉的巨集。「真實程式語言是圖靈完備的」這個論題，正是為什麼這是關於你的 Python 與你的 C 的事實，而不只是關於理想化機器的事實。
- 先決定：當機器拿到自己的描述後，你要它做什麼。把它寫成一台兩輸入機器 T(w, x)：把 w 當成「我自己程式碼的副本」、x 當成真正的輸入，然後做證明所需的任何事——例如「拿 w 與 x 比較」或「把描述 w 在 x 上運行」。
- 把 T 交給遞迴定理。它回傳單一的一台機器 R，其中 w 這個欄位已由 R 自己的描述自動填好——沒有無窮回退，靠的是底層那個 quine 風格的構造。
- 現在就把 R 當成「讓我把自己的原始碼抓進變數 w」這一行單純地成功了來推理。這一句獲准使用的詞，就是你得到的全部能力，而它已足以推動出意外俐落的證明。
把它當證明工具：A_TM，以及被嚴謹化的說謊者
遞迴定理把最滑溜的不可判定性證明變成兩行論證。重新證明接受問題 A_TM 不可判定，這回完全不用對角線表格。為了反證，假設存在一個判定器 H，它總會停機、並正確地告訴你某台機器是否接受某個給定輸入。用以下方式建一台機器 B，動用定理去抓取 B 自己的描述：在輸入 x 上，B 取得自己的程式碼，問 H「B 是否接受 x」，然後做出與 H 判決相反的事。現在拿任何輸入跑 B。若 H 說「B 接受」，B 就拒絕；若 H 說「B 拒絕」，B 就接受。對每一個輸入，H 對 B 的判斷都錯——所以那個永遠正確的 H 不可能存在。
再讀一次，注意那份不自在消失了。先前的證明需要一個像「把機器在自己的程式碼上運行」的自我應用，而那總會招來一句「等等，這真的被允許嗎？」。如今答案是「是」，由定理保證：B 抓取自己的描述，是一個完全獲准、有限的操作。剩下的純粹是說謊者悖論——「這句話是假的」被編譯成一台「對 H 預測它什麼、它就唱反調」的機器。遞迴定理正是那座橋，讓非正式的說謊者變成嚴謹的機器，這也是為何它是停機問題背後那個對角線論證最乾淨的包裝。
同一個「一步」把戲，能漂亮地重證萊斯定理（Rice's theorem）。要證明某個語言的非平凡性質不可判定，就建一台機器：它抓取自己的程式碼、把那個假想的性質判定器用在自己身上，然後刻意去辨識一個具有相反性質的語言。無論判定器對這台機器宣稱什麼，這台機器都被接線成去反駁它。沒有對角線記帳、沒有列舉——只是「讓我看看自己，再駁倒你的判決」。這就是遞迴定理在賺它的伙食費。
圖靈歸約、神諭，與更大的地圖
退回這一階的主線。映射歸約（多對一歸約，many-one reduction）在兩個問題都還沒被解決之前，就把一個問題翻成另一個，並俐落地同時傳遞不可判定性與不可辨識性。但有一個更鬆、更強的概念值得命名：圖靈歸約（Turing reduction）。這裡你被允許這樣解問題 A：為它寫一個普通演算法，而這個演算法可以隨它高興呼叫問題 B 的一個子程式任意多次，並把那個子程式當成一個永遠回傳正確答案的黑箱。那個假想的完美子程式就是一個神諭（oracle）——一個你問是非題、永遠得到真相的魔法助手。
何必用一個較弱的工具？因為圖靈歸約能做映射歸約做不到的事，而這道落差很有啟發性。A_TM 的補集不能由 A_TM 用映射歸約得到（一個是不可辨識的、一個是可辨識的，而映射歸約無法跨越那條線）。但 A_TM 圖靈歸約到它的補集則輕而易舉：只要呼叫神諭、把答案反過來就好。所以圖靈歸約對「可辨識／余可辨識」之分視而不見，這恰恰是為何當你想傳遞不可辨識性時，映射歸約才是正確、更精細的工具——這是本階稍早的一個論點，如今有了名字附在上面。
神諭也把超越單純不可判定性的地景組織起來。想像給一台圖靈機配上一個停機問題的神諭；仍有些問題它解不了，於是你可以再問一個關於那些問題的神諭，如此下去。把這些層級堆疊起來，便得到算術階層（arithmetical hierarchy）——一把量度不可解程度的尺：不可判定並非單一樓層，而是一整座高塔。你在這裡不需要它的細節；要記住的是，「不可判定」是一個豐富結構的地面層，而圖靈歸約加上神諭，就是在樓層之間移動的電梯。
該記住什麼，又該避免過度宣稱什麼
離開前做兩個誠實檢查。第一，遞迴定理並不讓一台機器預測自己未來的行為——它只讓機器讀取自己靜態的描述。B 能抓取自己的程式碼，卻依然無法判定自己是否會停機；事實上 A_TM 不可判定的證明，恰恰就是：沒有任何機器，無論是否「有自知」，能逃出那堵停機之牆。自我指涉給的是對你文本的存取，而不是對你運行的先知。把這兩者混為一談是最常見的過度宣稱，而那是錯的。
第二，把自我指涉與難解放進不同的盒子，正如你把不可判定與只是難分開。遞迴定理談的是可計算性——究竟能不能做——它對代價隻字不提。quine 很便宜；A_TM 不可能；一個 NP 完全的謎題可判定卻昂貴。這些活在不同的軸上。這條定理是關於程式碼自我認識之可能性的陳述，與執行時間無關，它既不會讓任何東西變快，也不會讓任何東西變慢。
現在把你剛走完的整階拉遠來看。歸約是個翻譯器，而方向就是一切：你把一個已知難的問題翻進你的問題，於是你的問題繼承了那份難度。映射歸約是那個精確的版本，它連不可辨識性也一起搬運；圖靈歸約與神諭則是更鬆、更強的表親，也是一整座不可解階層的起點。而遞迴定理是引擎蓋下那具安靜的引擎——它是「機器何以能合法地對自己推理」的理由，於是對角線論證核心的那個說謊者悖論，不是謬誤，而是一條定理。有了這些，你便能把不可判定性當成一顆種子，種出一整座不可能問題的花園——這正是這一階一開始就要交到你手中的能力。