用歸約證明不可判定性（proving undecidability by reduction）

一旦你從頭證明了某個問題不可能，往後你幾乎不必再做那種苦工。不可判定性會像傳染病一樣擴散。技巧是論證：如果我能解這個新問題，那我就能解停機問題，而那是不可能的，所以這個新問題也必定不可能。這是「若你能，則我也能；但我不能，所以你也不能」的證法。已知的不可能性是種子；歸約是把它吹向四方的風。

這套做法有固定的形狀。要證明新問題 B 不可判定：(1) 挑一個已知不可判定的問題 A，經典的選擇是接受問題 A_TM 或停機問題；(2) 為了導出矛盾，假設 B 有判定器，一台永遠停機並給出正確是或否的機器；(3) 把這個假想的 B 判定器當子程式用，建造出一個 A 的判定器；(4) 但 A 沒有判定器，矛盾，所以 B 也沒有判定器。步驟 (2) 與 (3) 合起來正是歸約 A <= B，常以映射歸約實現：一個可計算函數把每個 A 實例變成 B 實例，並把是保持為是。整個論證是把反證法包在歸約外層。

把方向弄對就是一切：你把已知很難的 A 歸約到你的新 B，絕不反過來（見「歸約方向」）。做對了，這單一範本就能起訴一整列問題：圖靈機的空集、等價、正規性與全域性問題，並透過波斯特對應問題，連帶一大批文法問題。另有一條更俐落的替代路徑用遞迴定理，直接建造一台自指機器、繞過顯式歸約；但歸約範本仍是你最常伸手去拿的那一個。