遞迴可枚舉語言（recursively enumerable language）

現在換一位圖書館員：她誠實，但不一定準時。如果你要的書是館藏，她最後一定會把書高舉說「有」——也許找了很久，但她終究會說。如果你要的書館裡沒有，她可能說「沒有」，也可能一直在書架間翻找下去、永遠不回來。所以「有」一定會在有限時間內送達，但「沒有」無法保證。遞迴可枚舉語言就是這種單邊機器所接受的字串集合。

形式地說，語言 L 是遞迴可枚舉的（RE），也叫圖靈可識別（Turing-recognizable），如果存在某台圖靈機 M 識別它：對每一個 w ∈ L，M 在 w 上執行最終會停機並接受；對每一個不屬於 L 的 w，M 要嘛停機並拒絕、要嘛永遠執行下去（迴圈）。機器被允許「恰好在 L 之外的字串上迴圈」。所以接受是一個可靠的訊號——只要你看到「接受」，答案就真的是「有」——但「沒看到接受」可能代表「沒有」，也可能代表「還沒算完」，而你從外面永遠分不出是哪一種。

每一個遞迴（可判定）語言都是遞迴可枚舉的——一台總會停機的機器當然識別它的語言——所以 RE 是一個嚴格更大的盒子，裝下所有可判定語言還多一些。最著名的那位「多出來的住戶」就是圖靈機的接受問題（機器 M 是否接受輸入 w？），它可識別但不可判定。「遞迴可枚舉」這個名字來自一個漂亮的等價觀點：L 是 RE，恰好等於「存在某台機器能把 L 裡的每個字串一個一個印出來」——它能枚舉（enumerate）它的成員，即使永不結束。