共可識別語言（co-recognizable language）

我們看過：可識別的機器能可靠地喊「是」，但碰到「否」可能沉默。共可識別語言把可靠訊號翻到另一邊：它的機器能可靠地喊「否」（這個字串不在語言裡），但碰到「是」可能沉默。想像一位嚴格的警衛：他確定某人在黑名單上時會立刻把人擋下，但對不在名單上的人，他會無限期地查檔案、卻從不放行。共可識別語言，恰好就是某個可識別語言的補集。

形式地說，語言 L 是共可識別的（共遞迴可枚舉），如果它的補集——Σ（Sigma）上所有「不在 L 裡」的字串所成的集合——是可識別的。等價地說，存在一台機器，對每個不在 L 裡的 w 最終都會停機並回報「非成員」，而對 L 的成員則可能永遠迴圈。所以共可識別的意思是：你能確認的是「非成員」。依定義，共可識別語言恰好就是可識別語言的補集，與之互為鏡像。

這個類別是一個漂亮對稱的另一半。可識別語言抓住它們的「是」；共可識別語言抓住它們的「否」。只落在其中一個盒子的語言必然不可判定（你只能確認一個方向、無法確認另一個）。而同時落在兩個盒子裡的語言——既可識別又共可識別——結果恰好就是可判定語言，因為這時你能用一邊確認「是」、用另一邊確認「否」，再把它們合成一個總會停機的程序。典型的「共可識別但不可識別」例子，就是圖靈機接受問題的補集。