從口號到一台精確的機器
上一篇裡，歸約是一句口號加一個翻譯器：「如果我能解決 B，我就能解決 A」，於是 A 的困難會沾染到 B 身上。這個直覺是對的，但口號不會傳遞不可能性——一個謹慎的定義才會。最乾淨的那個，就是映射歸約（也叫多對一歸約）。它要求的，不是兩個問題之間一來一往的巧妙對話，而是事先做好的一次誠實、固定的翻譯，由一台永遠會停機的機器來計算。
把定義用話說出來。語言 A 映射歸約到語言 B（寫成 A <=m B），若存在一個全可計算函數 f——一台對每個輸入都會停機的圖靈機——使得對每個字串 w，w 在 A 中若且唯若 f(w) 在 B 中。「若且唯若」這四個字扛起了全部的重量：f 必須把 A 的「是」實例送到 B 的「是」實例，而且把「否」實例送到「否」實例。它是「屬於與否」這件事的忠實翻譯者，在任一方向上都不撒謊。注意 f 不必判定任何事；它只是把問題改寫了一遍。
為何這個翻譯器會傳遞可判定性
整個定義的重點，就是一條短短的推理鏈。假設 A <=m B 經由 f，並且——讓我們開心一刻——假設 B 是可判定的，有一台判定器 D_B，永遠以「是」或「否」停機。那麼我們就能用現成零件拼出一台 A 的判定器：給定 w，先跑 f 把它翻成 f(w)，再把 f(w) 交給 D_B，然後原樣轉述它的答案。因為 f 永遠停機、D_B 也永遠停機，這台組合機器永遠停機。又因為 w 屬於 A 恰好當 f(w) 屬於 B，轉述出的答案就是正確的。於是 A 也會是可判定的。
現在把它翻成逆否命題，那才是你真正會用的形式。若已知 A 是不可判定的，且 A <=m B，那麼 B 也必定不可判定——因為若 B 有判定器，上面那個構造就會交給我們一台 A 的判定器，和「A 沒有判定器」相矛盾。這正是不可判定性的傳遞，也正是第一篇那個方向變得攸關生死之處。你要把箭頭從已知困難的 A 指向你的新目標 B。把停機問題歸約到 B，絕不是把 B 歸約到停機問題。把箭頭搞反，你就只證明了你那個容易的問題不比一個困難的問題更難——一句正確卻無用的話。
KNOWN HARD YOUR TARGET
A = A_TM --------- f ---------> B = ???
(undecidable) mapping (you want to show undecidable)
Build a decider for A out of: [ translate w into f(w) ] --> [ decider for B ] --> echo answer
If B had a decider ==> A would too ==> contradiction ==> B has no decider.
Arrow rule: reduce the KNOWN-hard problem TO your new one (A <=m B).
Backwards (B <=m A) proves nothing about B's hardness.它也載著那個較弱的承諾：可辨識性
映射歸約很慷慨：同一個翻譯器傳遞的不只是可判定性。它也搬運可辨識性——那個較弱的承諾：一台機器對每個「是」實例都會說「是」，但對「否」實例可能永遠繞圈。把論證換成辨識器再跑一遍：給定 w，算出 f(w)，餵給一台 B 的辨識器。若 w 在 A 中，則 f(w) 在 B 中，辨識器接受；若 w 不在 A 中，則 f(w) 不在 B 中，辨識器要嘛拒絕、要嘛繞圈——而那恰恰是一台 A 的辨識器被允許有的行為。所以若 B 可辨識且 A <=m B，則 A 可辨識。
再取一次逆否命題，你就得到最鋒利的那件工具：不可辨識性的傳遞。若已知 A 是不可辨識的，且 A <=m B，則 B 不可辨識。揮舞它的標準手法有個小轉折。從第一篇的鄰里你知道，通用接受語言的補集，也就是語言 NOT-A_TM，是不可辨識的。一個關於映射歸約的好用事實一錘定音：A <=m B 成立若且唯若（A 的補集）<=m（B 的補集），因為同一個 f 對兩者都管用——無論你把哪一邊叫作「是」，它都尊重那個雙條件。所以要證明某個 B 不可辨識，你常把 A_TM 歸約到 B 的補集；那等同於把 NOT-A_TM 歸約到 B，於是不可辨識性便搭著它過了河。
一列倒下的問題
有了一具引擎和一個困難的源頭，你就能推倒一整排骨牌。拿圖靈機的空性來說——給定的機器 M 是否一個字串都不接受、它的語言是否為空？把 A_TM 歸約到它：給定 (M, w)，造一台新機器 M'，它無視自己的輸入，在固定的 w 上模擬 M，僅當 M 接受 w 時才接受。於是當 M 接受 w 時，M' 接受一切（非空語言）；當 M 不接受 w 時，M' 什麼都不接受（空語言）。所以判定 M' 的空性，就等於判定 M 是否接受 w——但那就是 A_TM，不可判定。空性倒下。那個從 (M, w) 造出 M' 的函數顯然是全函數且可計算，所以這是一個合法的映射歸約。
從空性出發，兩台圖靈機的等價性（M_1 與 M_2 是否辨識同一個語言？）幾乎免費就倒了：空性不過是「M 是否等價於一台拒絕一切的機器？」這個特例，所以一台等價性判定器就能判定空性。同樣的傳染還伸得比機器更遠。波斯特對應問題——一個關於把骨牌排好、使上排與下排字串相符的謎題——透過一個（更精巧的）從停機問題出發的歸約而不可判定，做法是把一台機器的計算歷史編碼成一場骨牌相符遊戲。而一旦 PCP 倒下，它便成了那把鎚子，敲死好幾個文法問題：一個上下文無關文法是否有歧義，以及兩個上下文無關文法是否生成同一個語言。這一階接下來兩篇會把這兩個故事完整講出來。
把規則放寬：圖靈歸約與神諭
映射歸約是個嚴格的、一次性的翻譯器：把問題改寫一次、問 B 一次、原樣轉述 B 的答案。有時這太僵硬了。較寬鬆的版本是圖靈歸約，建立在神諭機器之上——一台普通的圖靈機被授予一項超能力：一位神奇的顧問，問題 B 的神諭，它能立刻回答任何關於 B 的「屬於與否」是非問題。圖靈歸約說：A 可由一台機器解出，這台機器想諮詢 B 神諭多少次就多少次、用任何模式都行，並能在判定 A 之前自由地組合、否定那些答案，或依答案分支。把 B 想成一個你可以反覆呼叫的副程式，而非一次做完的翻譯。
這份自由買來了真本事。每個映射歸約都是一個圖靈歸約（呼叫神諭一次、原樣轉述），但反過來不成立。乾淨的例子是：一個語言和它的補集永遠是圖靈等價的——有了 B 的神諭，你只要問神諭再把答案翻轉，就能判定 B 的補集。然而一個語言可能無法映射歸約到它自己的補集（A_TM 與 NOT-A_TM 在可辨識性上的差異正是如此）。所以圖靈歸約嚴格地更有彈性。這份彈性誠實的代價是：圖靈歸約忠實地傳遞可判定性——若 B 可判定且 A 圖靈歸約到 B，則 A 可判定——但它不保存可辨識性，因為它可能去問神諭關於「否」實例的事並依那個「否」行動，而那是一台單純的辨識器做不到的招。若只為證明不可判定性，圖靈歸約就夠用，而且往往更省事；但要那些更精細的不可辨識性結果，你就得守著映射歸約。
遞迴定理：一台認得自己的機器
自從停機問題的證明以來，有一條線頭一直在拉扯。那個證明造了一台機器，去問關於它自己描述的事，然後反其道而行——但一台機器真的可以合法地拿到它自己的程式碼嗎？遞迴定理說可以，乾乾淨淨、而且完全一般地成立：任何圖靈機都能在運作的過程中，取得它自己完整的描述並用它來計算。最令人腦袋打結的地方在於，這裡沒有無窮回歸，沒有哪台機器非得永遠含著一份含著它自己副本的機器副本。一台有限的機器，可以指涉它自己（有限的）程式碼。你早已見過的日常表親，就是奎因（quine）——一支不讀任何輸入、也不讀自己檔案，就印出自己原始碼的程式。
遞迴定理一身二用。作為一個結果，它馴服了自我指涉：在計算裡，自我指涉並不弔詭、也不被禁止；它是一項稀鬆平常、隨手可用的能力。作為一件證明工具，它是一份禮物，因為它讓你能寫出這樣的證明：「設 M 是一台機器，它運用自己的描述，做以下的事……」而不必揮舞任何循環論證的手。舉例來說，你可以一筆證明 A_TM 不可判定：假設存在一台停機判定器 H；造一台機器 R，它取得自己的描述 angle-bracket R angle-bracket，問 H 自己是否會在其輸入上停機，然後做出與 H 的預測相反的事。R 在自己的行為上和 H 相矛盾，所以 H 不可能存在。這就是停機證明裡那個對角線式的自我指涉，如今被遞迴定理授了權、化為了例行公事。
- 先定方向：要證明你的目標 B 困難，就把 A 設為一個已被證明困難的問題（A_TM、停機問題，或它們下游的任何問題），並瞄準 A <=m B——絕不是 B <=m A。
- 設計一個全可計算函數 f，把 A 的每個實例映到 B 的一個實例，使得「是」實例去到「是」實例、「否」實例去到「否」實例（那個雙條件）。
- 用追蹤「是」情形與「否」情形來驗證雙條件的兩個方向，並確認 f 永遠停機。任一方向的滲漏都會作廢這個歸約。
- 以逆否命題作結：既然 A 不可判定（或不可辨識）且 A <=m B，B 便繼承了同樣的不可能性。若你只需要不可判定性，一個圖靈歸約（帶神諭、或許多次查詢）同樣行得通。