圖靈可判定（Turing-decidable）

圖靈可判定語言，是某台機器像一位無懈可擊、從不卡住的保鏢般處理的語言：無論看到誰的證件，是會員與否，他總在有限時間內做出堅定的決定、說是或非。不會永遠盯著、不會僵住、不會「待會再來」。每個字串都得到清楚、正確的裁決，而機器總會停下來給出它。

形式上，語言 L 是圖靈可判定的（也稱遞迴語言），若存在一台圖靈機 M，它對「每一個」輸入都停機，且恰好接受 L 中的字串：對 L 中的字串停在 q_accept，對不在 L 中的字串停在 q_reject。兩項要求合起來才是重點：正確性（接受成員、拒絕非成員）「以及」對所有輸入都保證停機、絕不迴圈。這樣的機器稱為判定器。判定一個語言，正是「擁有一個總會終止、總能正確回答成員問題的演算法」之精確形式化。

可判定性是黃金標準：可判定問題就是你真能用一個保證會結束的演算法解決的問題。它嚴格地位於圖靈可識別之內：每個可判定語言都可識別（判定器本就是一種識別器），反之不然，因為識別器可能對非成員迴圈。一個漂亮的定理把它們繫在一起：語言可判定，當且僅當它「與」它的補集都是圖靈可識別的。這正是為什麼證明停機問題的補集不可識別，就證明了停機問題不可判定。