遞歸集合

自然數的子集 空集 素數的集合

在可計算性理論中，一個可數集合被稱為遞歸的、可計算的或可判定的，如果我們可以構造在有限數量的時間之後終止並判定一個給定元素是否屬於這個集合的算法。更一般的集合的類叫做遞歸可枚舉集合。這些集合包括可判定集合，但只要求它們在有限時間內停止於是或否(或二者，這使集合可判定)。
定義
f為S到N的映射關係
自然數的子集 S 被稱為遞歸的，如果存在一個全可計算函式
使得
若x屬於S則f(x)等於0
若x不屬於S則f(x)不等於0
換句話說，集合 S 是遞歸的，若且唯若指示函式 1S 是可計算的。
例子
空集
自然數
自然數的所有有限子集
素數的集合
遞歸語言是在形式語言字母表之上所有可能詞的集合中的遞歸集合。
性質
如果 A 是遞歸集合，則 A 的補集是遞歸集合。 如果 A 和 B 是遞歸集合，則 A ∩ B、A ∪ B 和 A × B 是遞歸集合。集合 A 是遞歸集合，若且唯若 A 和 A 的補集是遞歸可枚舉集合。一個遞歸集合在全可計算函式下的原像(preimage)是遞歸集合。