圖靈可識別（Turing-recognizable）

想像一位保鏢，他正確地放進俱樂部的每位會員，但面對非會員時，有時只是永遠盯著對方的證件、從不說「不」。他從不錯放任何人，也從不把會員錯擋在外，卻可能對局外人無止盡地僵住。圖靈可識別語言就是某台機器像這位保鏢般處理的語言：它接受每個屬於的字串，但對不屬於的字串，它可能拒絕，也可能就此永遠迴圈。

形式上，語言 L 是圖靈可識別的，若存在一台圖靈機 M，使 M 恰好接受（停在 q_accept）L 中的字串，而對每個不在 L 中的字串，機器要嘛拒絕、要嘛永遠運行。唯一的承諾關乎成員：每個成員終究會被接受。沒有承諾的部分關乎非成員：機器被允許永遠不給明確的「不」。所以若你對某字串跑 M 而它接受了，你就得知該字串在 L 中；但若它還沒接受，你不能斷定它不在 L 中，因為它也許稍後才接受，也許永遠迴圈。

圖靈可識別是這部分理論中最廣的自然類別，而且嚴格大於可判定類：有些語言可識別卻不可判定，通用語言 A_TM 就是標準例子。較舊的名稱是遞迴可枚舉（recursively enumerable, r.e.），因為這樣的語言恰好是某台機器能逐一列出的語言，雖然不一定按順序、也不一定列得完。誠實的結語：可識別之所以確實弱於可判定，正是因為那被允許的迴圈；半判定一個問題是真實但有限的進展。