可判定 vs 可識別（decidable versus recognizable）

想像兩種客服中心。第一種每一次都會回電給你一個明確答案，是或否——你可以照它規劃一整天。第二種：只要答案是「是」，它就會回電說「是」；但碰到「否」時，它有時就乾脆沉默，讓你無限期地守在電話旁。兩種都能確認「是」。只有第一種還能確認「否」。這個差別——保證會結束 vs 可能永遠沉默——正是可判定與可識別之間的鴻溝。

精確地說：語言是可判定的（遞迴），如果存在某台圖靈機對每個輸入都停機並給出正確的接受／拒絕——一個真正的判定程序。它是可識別的（遞迴可枚舉），如果存在某台機器恰好接受語言中的字串，但被允許在語言之外的字串上永遠迴圈。每個可判定語言都是可識別的（「總會停機」是「最終會接受」的特例），但反過來不成立：存在可識別卻不可判定的語言。標準的見證者是 A_TM = {(M, w) : M 接受 w}，通用機器靠模擬就能識別它，卻沒有任何機器能判定它。

為什麼要堅持這個區分？因為它正是「電腦原則上能解決並保證給出答案」與「電腦能確認『是』但可能永遠無法確認『否』」之間的分界線。實務上這意味著：對可判定問題，你可以寫個程式安心等它跑完；對僅僅可識別的問題，在答案為「否」的情況下你的搜尋可能永遠跑下去，而你沒有辦法知道該繼續等還是放棄。下一個定理把這一切綁在一起：一個語言可判定，恰好等於它與它的補集都可識別。