在數學、邏輯學和計算機科學中，如果一種形式語言是該語言字母表上所有可能的詞語集合中的一個可遞歸可列舉的子集，也就是說，如果存在一臺圖靈機可以列舉出該語言的所有有效字符串，那么該語言就被稱為遞歸可列舉（也是可識別的、部分可解的、半可解的、圖靈可接受的或圖靈可識別的）。可遞歸列舉的語言在喬姆斯基形式語言的等級體系中被稱為0型語言。所有正規的、無語境的、對語境敏感的和遞歸的語言都是可遞歸列舉的。所有可遞歸枚舉語言的類別被稱為RE。定義遞歸可列舉語言有三個等價的定義。遞歸可列舉語言是在該語言的字母表上所有可能的詞的集合中的一個遞歸可列舉的子集。遞歸可列舉語言是一種形式語言，對于這種語言存在一個圖靈機（或其他可計算的函數），可以列舉出該語言的所有有效字符串。請注意，如果語言是無限的，所提供的枚舉算法可以被選擇，以避免重復，因為我們可以測試為數字n產生的字符串是否已經為一個小于n的數字產生。

遞歸可列舉語言是一種存在圖靈機（或其他可計算函數）的形式語言，當輸入該語言中的任何字符串時，它將停止并接受，但當輸入不在該語言中的字符串時，它可能停止并拒絕或永遠循環。這與遞歸語言形成對比，后者要求圖靈機在所有情況下都能停止。所有正規的、無語境的、語境敏感的和遞歸的語言都是可遞歸列舉的。波斯特定理表明，RE與它的補數co-RE一起，對應于算術層次的xxx層。

終止圖靈機的集合是可遞歸列舉的，但不是遞歸的。事實上，人們可以運行圖靈機并接受機器是否停止，因此它是可遞歸列舉的。另一方面，這個問題是不可判定的。其他一些非遞歸可列舉的語言包括。

死亡率(可計算性理論)Entscheidungsproblem封閉屬性遞歸可列舉語言(REL)在下列操作下是封閉的。也就是說，如果L和P是兩個可遞歸列舉的語言，那么下面的語言也是可遞歸列舉的。遞歸可列舉語言在集差或補足下是不封閉的。集合差分{displaystyleL}{displaystyleP}是可遞歸枚舉的，如果P{displaystyleP}是遞歸的。是遞歸的。如果L{displaystyleL}是可遞歸的。是可遞歸列舉的，那么L的補集L{的補集｝的補集是可遞歸列舉的，當且僅當L{displaystyleL}的補集也是遞歸的。也是遞歸的。