接上線索：從一個不可能的問題到一群
上一階結束時，你已擁有一小批珍貴的不可能。停機問題——給定一台機器與一個輸入，它最終會停機還是永遠繞圈？——沒有任何永遠正確作答的演算法，而我們用一個把機器餵給它自己描述的對角線論證把這個事實逼到了死角。我們也認識了它的近親接受問題 A_TM（這台機器接受這個輸入嗎？），用同樣的辦法證明它不可判定。這些結果滴水不漏，卻很孤單：每一個都是徒手證出來的。下一個自然的念頭是：每碰到一個我們懷疑不可能的新問題，難道都得把那套精巧的對角線論證重做一遍嗎？
幸好不必。有一根可重複使用的槓桿，它正是整個這一階的引擎。歸約一言以蔽之，就是把一個問題翻譯成另一個問題的翻譯器。如果我能把關於問題 A 的每個提問，翻譯成關於問題 B 的等價提問——使得解開 B 就自動解開了 A——那麼 A 不會比 B 更難。把這句話倒過來，就得到我們將反覆狠用的版本：如果 A 已知不可能，那 B 也必定不可能，因為一台 B 的解算器就會交給我們一台 A 的解算器。一個頑固的不可能——停機問題——如今能感染每一個我們能把它歸約過去的問題。
箭頭該朝哪邊指？
規則來了，講得讓你能把它刺在眼皮內側。要證明你的新問題 B 不可判定，你要把一個已知不可判定的問題 A 歸約到 B。我們寫作「A 歸約到 B」，或「A <= B」，讀作「A 不會比 B 更難」。已知很難的東西坐在左邊，你懷疑很難的目標在右邊。箭頭從已確立的不可能，流入你想定罪的新問題。這就是歸約方向的全部，而你這輩子會寫的幾乎每個不可判定性證明，都是它的一個實例。
為什麼方向關係如此重大？因為「A <= B」只把不可能往一個方向搬運。它說一台 B 的解算器產出一台 A 的解算器，所以「B 可解」會逼出「A 可解」。我們把這句取逆否——用你在基礎篇學過的逆否命題翻轉它——成「A 不可解，所以 B 不可解」。A 的難度往下坡流入 B。它不會往另一邊流：知道你的問題 B 很難，對 A 一無所言；而把你的問題歸約到停機問題，對你的問題什麼也證明不了。那個反向的歸約是真實存在的、有時甚至成立，只是作為難度證明毫無用處。
一個鮮活的心算檢查能把方向永遠釘住。你想證明你的問題 B 很難。你為了導出矛盾，假想出一台 B 的魔法解算器。現在你——這位證明的撰寫者——必須去建一台著名難題 A 的解算器，並把 B 的魔法解算器當成子程序來用。於是你寫一個翻譯器：拿 A 的任一實例，把它變成 B 的一個實例，跑那台魔法 B 解算器，再讀出 A 的答案。如果這個翻譯器存在，那一台 B 解算器就能擊敗停機問題，而那是不可能的；所以這台 B 解算器不可能存在。注意這份工：你把 A 翻譯成 B。你永遠是在用新問題假想出的能力去攻擊那個已知不可能的問題。
兩種風味的歸約：映射與圖靈
並非所有翻譯器都同樣乾淨，現在值得區分出兩種風味。最俐落的是映射歸約（又稱多對一歸約）。它是單一個可計算函式 f，把每個輸入 w 改寫成一個新輸入 f(w)，並帶著一個鐵鑄的承諾：w 是 A 的「是」實例，恰恰就在 f(w) 是 B 的「是」實例的時候。不准偷看答案、不准呼叫第二次——你只翻譯一次、只問 B 的解算器一次，而 B 對 f(w) 的裁決就是對 w 的裁決。正因為「是／否」是精確對應的，一個從 A 到 B 的映射歸約不只搬運不可判定性，還搬運不可辨識性——這種更細緻的搬運是下一篇要倚重的。
更寬鬆的風味是圖靈歸約，建立在一個迷人的虛構之上，叫做神諭機。想像一台普通的圖靈機——你那本無盡的可重寫筆記本——但它擁有一支魔法電話。任何時刻它都能在一條特殊紙帶上寫下一個問題，然後在一步之內聽到關於某個固定問題 B 的完美是／否答覆。那位接電話的，就是神諭。一個從 A 到 B 的圖靈歸約，就是任何一台一邊判定 A、一邊向 B 神諭撥電話的神諭機——而關鍵在於它可以撥很多次、用先前的答覆決定下一步問什麼，甚至把神諭的回覆反轉。它是「如果我能解 B，我就能解 A」最寬容的一種意思。
為何兩個都留著？映射歸約很嚴格——一次呼叫、答案分毫對齊——而這份嚴格，正是讓它們能搬運「可辨識」與「可判定」之間那條細緻分界的關鍵。圖靈歸約較鬆，能在單一乾淨映射辦不到的情形下證明不可判定，但那份讓它能反轉答案的彈性，恰恰意味著它不尊重那條細線：圖靈歸約可以把一個問題連到它的補集，所以分不出可辨識與可餘辨識。誠實的經驗法則：每個映射歸約都是一個（極為自律的）圖靈歸約，反之則不然。當你只需要「B 不可判定」，兩者皆可；當你需要「B 不可辨識」，就拿出映射歸約。
一排被定罪的問題
握著這根槓桿，不可判定問題的清單長得飛快——而一趟導覽便能看出停機問題的陰影伸得有多遠。在圖靈機的提問裡，空語言（這台機器是不是一個字串都不接受？）與等價（這兩台機器接受的語言是否一模一樣？）都不可判定；兩者各由一個從接受問題出發的歸約倒下。這些不是「只是慢」、換台更快電腦就能解的問題——它們根本沒有正確的通用演算法，與停機問題不可能的那種強烈意義相同。別把這層意思軟化掉：不可判定指的是可被證明沒有演算法，而非「實務上很難」。
某些最有用的不可判定問題根本不提機器。下兩篇的主角是波斯特對應問題：給你一疊像骨牌的牌，每張帶著一個上方字串與一個下方字串，你得判定是否存在某個牌的序列（可重複）使串接後的上方讀起來與串接後的下方相同。它聽起來像個天真的文字謎題，然而波斯特對應問題不可判定——又因為它純粹關乎字串配對，它成了攻擊文法相關問題的完美武器。好幾個自然的文法問題都死在它手裡，最有名的是判定兩個上下文無關文法是否生成同一語言，以及判定一個給定文法是否含糊。
還有一條批發式的定理，整批地定罪各種性質：萊斯定理。它說一台機器所辨識之語言的任何非平凡性質都不可判定——「這台機器接受的是有限語言嗎？」「它的語言是空的嗎？」「它辨識的是質數嗎？」全部一次倒下。容易讀錯的關鍵小字：萊斯定理講的是語言的性質（輸入／輸出行為），而非程式碼的語法性質。「這台機器剛好有 12 個狀態嗎？」或「它的描述裡含有字母 q 嗎？」都是完全可判定的——你看一眼文字就好。萊斯只在問題是關於機器計算什麼、而非它怎麼寫的時候才咬人。
遞迴定理：一台認得自己的機器
這一階還要介紹最後一件工具，在你看見它的齒輪之前，它感覺像個魔術。遞迴定理說：任何機器都能免費取得它自己的描述。更精確地說，如果你能描述一段想把「我自己的原始碼」當成一個值來用的計算，那就真的存在一台機器恰好做到這件事，並把它自己完整的描述擺在紙帶上交給它。這聽起來循環——一個程式怎能包含它自己的文字，而那文字又得包含那文字，無窮無盡？——但它確實可能，最小的例子是一個奎因，一個唯一任務就是印出自己原始碼的程式。
遞迴定理戴著兩頂帽子。作為證明工具，它讓自我指涉變得體面又乾淨：你不必再做那套繁瑣的對角線體操，只要直接說「設 M 是一台取得自己描述、然後做以下事情的機器……」，定理就保證這樣的 M 存在。這讓「停機問題不可判定」的證明流暢起來：造一台機器，去問那台假想的停機檢查器關於它自己的事，然後故意做相反的事——若被預測會繞圈就停機、若被預測會停機就繞圈——這個矛盾需要那台機器握有它自己的描述，而那正是定理所供給的。作為一個結果，它是個深刻的陳述：自我指涉並不弔詭，而是計算與生俱來、無害的能力。
Reduction layout (the shape of every proof in this rung):
KNOWN-undecidable ----- reduces to -----> YOUR new problem
A_HP B
(halting problem) f (your target)
To prove B undecidable, BUILD this translator:
assume a decider R for B (the hypothetical magic solver)
construct decider S for A_HP:
on input <M, w>:
1. transform <M, w> into an instance x of B <- you write f
2. run R on x
3. report R's answer (possibly flipped) as the answer for A_HP
Then S decides the halting problem -- IMPOSSIBLE.
So R cannot exist, hence B is undecidable.
Arrow points FROM the known-hard problem INTO your new one.
Reverse it and the proof collapses to nothing.該帶上樓梯的東西
退一步看看剛才改變了什麼。在這一篇之前，不可判定性是一把孤立、徒手造出的結果。現在你有了一條生產線：找出一個已知不可能的問題，寫一個把它的提問轉成你目標之提問的翻譯器，不可能就免費地往下坡流入你的目標。這單單一個動作——以歸約證明不可判定性——是整套不可解理論的主力，而同樣的形狀，把「不可判定」換成「NP 困難」、把「可計算函式」收緊成「多項式時間函式」，稍後在樓梯上會回來驅動難解性的理論。
帶著三個誠實的提醒。第一，方向神聖不可侵犯：把已知很難的問題歸約到你的新問題，絕不反過來，否則你什麼也沒證——這是首要該提防的錯。第二，不可判定意味著真的沒有演算法，而非慢或只是困難；萊斯定理只咬語言的性質，不咬程式碼裡一眼可讀的語法。第三，風味有別：映射歸約嚴格到足以搬運不可判定性以及不可辨識性，而較鬆的圖靈歸約能反轉答案，因而分不出可辨識與可餘辨識。下一篇會把映射歸約講到完全精確，並一步步看著難度透過它擴散開來。