轉移不可判定性（transferring undecidability）

歸約之所以有用，是因為有東西沿著它傳遞。傳遞的就是可解性與它的缺席。轉移規則是引擎：映射歸約把可判定性由目標向源頭順流而下，因而把不可判定性由源頭向目標逆流而上。它像一根單向管：從一端倒入「B 可解」，另一端流出「A 可解」；等價地，從另一側推入「A 不可能」，便逼出「B 不可能」。

把它說清楚。假設 A <=m B，由可計算函數 f 實現。那麼兩條轉移事實是：（正向）若 B 可判定，則 A 可判定，因為要判定 A，你計算 f(w) 再對它跑 B 的判定器；以及（逆否，也就是你做難度證明真正會用的那條）若 A 不可判定，則 B 不可判定。第二條只是第一條的逆否讀法：若 B 有判定器，A 也會有，但 A 沒有，所以 B 不可能有。這就是為何單一顆不可判定性的種子——停機問題——能綻放成無盡的長廊：每個以不可判定的 A 做出的新歸約 A <=m B，立刻把 B 蓋上不可判定的章。

兩點誠實的提醒。其一，轉移只在已證明的方向上奏效：以不可判定的 A 做 A <=m B 才得到 B 不可判定；若你歸約錯方向，它並不告訴你 B 很難。其二，轉移傳遞的是性質，不是方法：知道 B 因 A 不可判定而不可判定，並不會交給你任何程序，因為兩者都沒有。歸約是邏輯的槓桿，不是演算法。同一套轉移機制，把「可判定」換成「多項式時間」，便再次現身為 NP 困難的骨幹。