不可識別語言（unrecognizable language）

我們看過可判定的語言（機器總會以正確答案停機）與僅僅可識別的語言（機器在成員上停機並接受，但在非成員上可能迴圈）。還有嚴格更難的一層：不可識別語言，對它而言沒有任何機器能「哪怕只做對一半」。不僅沒有判定器，連一個「能可靠接受成員」的識別器都沒有。這些是可計算性地圖上最深的坑。

計數論證早已許諾這類語言存在——語言有不可數多個，機器卻只有可數多台，識別器也是可數的，所以大多數語言不被任何機器識別。但我們也能具體指名一個。A_TM 的補集，寫成 co-A_TM（所有「M 不接受 w」的 (M, w) 之集合），就是不可識別的。理由建立在一條乾淨的定理上：一個語言可判定，恰好等價於「它本身與它的補集都可識別」。既然 A_TM 可識別卻不可判定，它的補集就不可能也可識別，否則這一對就會使 A_TM 變成可判定。

這補完了三層圖像：可判定包在可識別之內，可識別又包在所有語言之內，而 co-A_TM 完全落在可識別之外。一句好用的口號：可識別語言是機器能「確認成員資格」的語言（它最終會對每個成員說「是」），而不可識別語言裡有些成員是機器永遠無法可靠確認的。可識別性確實比可判定性弱，而不可識別性又更弱——不可能性是分層的，不只一層。