递归可枚举集

整数集合 被称为是递归可枚举的，如果它构成了一个递归函数的值域，即，如果存在一个递归函数，它可以最终生成 中的任何元素 (Wolfram 2002, p. 1138)。任何递归集合也是递归可枚举的。

两个递归可枚举集合的并集和交集也是递归可枚举的。

递归不可判定问题给出了非递归的递归可枚举集合的例子。例如， 的收敛性已知是递归不可判定的，其中 表示哥德尔数为 的图灵机。因此，所有使得 收敛的 x 的集合不是递归的。然而，这个集合是递归可枚举的，因为它是由如下定义的 的值域

(1)

一个集合 是递归的 当且仅当 和它的补集都是递归可枚举的。这提供了一种构建额外的非递归可枚举集合的方法。特别地，所有全图灵机的哥德尔数集合是一个非递归可枚举集合的例子。

递归可枚举但非递归集合的补集都不是递归可枚举的，尽管非递归可枚举集合的补集不一定是递归可枚举的。例如，所有全图灵机的哥德尔数集合的补集不是递归可枚举的。

递归可枚举集合的一个基本性质是，它们可以被替换地定义为定义域而不是值域。特别地，一个集合 是递归可枚举的 当且仅当 是一个递归函数的定义域。