保證停機（guaranteed to halt）

在這個領域所有用詞中，「保證停機」是那個承載重量的詞。它是把「你能信賴的演算法」與「可能讓你永遠空等的程序」分開的精確性質。一台保證停機的機器，像一座總會把答案滴答報完然後停下的時鐘，而不是那種可能無止盡滴答、卻從不鳴響的時鐘。這個保證，正是「可判定」所要求的，也正是「僅僅可識別」所無法提供的。

精確地說：一台圖靈機在某個輸入上停機，是指它在有限步後抵達接受狀態或拒絕狀態；若它無止盡地跑下去，就是永遠迴圈（不停機）。判定器是一台對『每個』輸入都停機的機器——沒有任何輸入會讓它迴圈。所以「L 可判定」意味著存在一台機器，對每一個可能的輸入，都保證會停機、並以正確的接受／拒絕判決停機。這個保證是普遍的（每個輸入）且無條件的（不論計算多長，都是有限的）。光是在 L 裡的字串上停機是不夠的；機器還必須在『不』在 L 裡的字串上停機——並拒絕。那後半段，正是純粹的識別器可能做不到的。

兩個誠實的提醒讓這個概念保持鋒利。第一，「保證停機」對『要花多久』隻字未提：一台判定器可能跑天文數字般多的步數。它是一個是非性質（它是否總會結束？），不是速度的度量；速度是複雜度理論的另一個議題。第二，這個保證對某些問題確實『不可能』提供。停機問題——某台機器在某個輸入上是否停機？——不可判定：沒有任何機器能保證停機並對所有輸入正確回答它。所以「保證停機」不是你只要夠聰明就總能安排的形式手續；它是一個真實、有時無法達成的性質，而「擁有它的問題」與「不可能擁有它的問題」之間那條線，正是下一個領域要探索的核心戲碼。