不可判定（undecidable）

一個問題是不可判定的，當沒有任何演算法能對每個輸入都正確解出它。更精確地說，語言 L 不可判定，是指不存在一台圖靈機，總會停機並恰好對 L 中的字串輸出「是」、對不在 L 中的字串輸出「否」。關鍵字是「總會停機」與「對每個輸入」：一個對許多情形有效、卻可能在某些情形卡住或出錯的方法不算判定器。不可判定是一個永久的、數學的判決，而非對今日硬體或我們當前聰明程度的評語。

把不可判定與兩種較溫和的情況對照會有幫助。可判定（也稱遞迴）問題有一個總會以正確答案停機的演算法——這是我們通常假設程式所處的舒適世界。可識別（遞迴可枚舉）但不可判定的問題，例如 A_TM，有一台機器在「是」的實例上停機並接受，卻可能在「否」的實例上永遠迴圈；它是半個判定器，只在「確認是」這件事上可靠。不可判定意謂不存在完整的判定器，儘管識別器有時存在；不可識別更難，意謂連識別器都不存在。

關鍵的誠實重點是：不可判定不等於難或慢。不可判定的問題不是「花很久時間」的問題，而是「在給定無限時間與記憶體下，沒有任何有限程序能在一般情形解決它」的問題。這與複雜度完全是不同的軸：複雜度問「一個可解問題有多貴」，而可判定性問「一個問題究竟可不可解」。停機問題、A_TM、程式等價，以及每個非平凡行為性質（Rice 定理），全都落在這條線的錯誤一側。