遞迴可列舉集

整數集合 被稱為是遞迴可列舉的，如果它構成了一個遞迴函式的值域，即，如果存在一個遞迴函式，它可以最終生成 中的任何元素 (Wolfram 2002, p. 1138)。任何遞迴集合也是遞迴可列舉的。

兩個遞迴可列舉集合的並集和交集也是遞迴可列舉的。

遞迴不可判定問題給出了非遞迴的遞迴可列舉集合的例子。例如， 的收斂性已知是遞迴不可判定的，其中 表示哥德爾數為 的圖靈機。因此，所有使得 收斂的 x 的集合不是遞迴的。然而，這個集合是遞迴可列舉的，因為它是由如下定義的 的值域

(1)

一個集合 是遞迴的 當且僅當 和它的補集都是遞迴可列舉的。這提供了一種構建額外的非遞迴可列舉集合的方法。特別地，所有全圖靈機的哥德爾數集合是一個非遞迴可列舉集合的例子。

遞迴可列舉但非遞迴集合的補集都不是遞迴可列舉的，儘管非遞迴可列舉集合的補集不一定是遞迴可列舉的。例如，所有全圖靈機的哥德爾數集合的補集不是遞迴可列舉的。

遞迴可列舉集合的一個基本性質是，它們可以被替換地定義為定義域而不是值域。特別地，一個集合 是遞迴可列舉的 當且僅當 是一個遞迴函式的定義域。