判定器（decider）

判定器（decider）是一台「總會做完」的圖靈機。給它任何輸入，它都保證在有限時間內停機，帶著明確的是（接受）或非（拒絕）。它永不卡在無窮迴圈裡。如果說一般的圖靈機是個可能放下工具、也可能永遠不放下的工人，判定器就是那個總會在某時放下工具、把裁決交給你的人。

形式上，判定器是一台對每個輸入字串都停機的圖靈機 M：對每個輸入，它在有限多步後進入 q_accept 或 q_reject，從不迴圈。判定器所識別的語言自動可判定，因為「總會停機」的保證加上正確的接受／拒絕行為，正是判定的定義。所以「判定器」是機器，「可判定」（或遞迴）是它所處理之語言的性質。設計判定器往往意味著加上迫使進展的記帳，例如劃掉符號，好讓機器無法無止盡地重訪同一情境。

判定器是可計算性誠實的主力：日常意義下的演算法，一個總會以正確答案終止的東西。整齣不可判定性的戲碼，談的正是那些「沒有」判定器能存在的問題，停機問題是頭條案例。值得標記的細微之處：每個判定器都是識別器，但多數識別器不是判定器，因為識別器被允許對非成員迴圈。把識別器變成判定器，正是你並不總能踏出的那一步；當你做不到時，問題就是不可判定的。