遞歸集合

在可計算性理論中，一個自然數的子集被稱為遞歸的、可計算的或具可判定性，如果我們可以構造一個算法，使之能在有限時間內終止並判定一個給定元素是否屬於這個集合。更一般的集合的類叫做遞歸可枚舉集合。這些集合包括遞歸集合，對於這種集合，只需要存在一個算法，當某個元素位於這個集合中時，能夠在有限時間內給出正確的判定結果，但是當元素不在這個集合中時，算法可能會永遠運行下去（但不會給出錯誤答案）。

定義

自然數的子集 S 被稱為遞歸的，如果存在一個全可計算函數

$f:S\to \mathbb {N}$

使得

$f(x)=\left\{{\begin{matrix}0&{\mbox{if}}\ x\in S\\\neq 0&{\mbox{if}}\ x\notin S\end{matrix}}\right.$

換句話說，集合 S 是遞歸的，當且僅當指示函數 $1_{S}$ 是可計算的。

例子

• 空集
• 自然數
• 自然數的所有有限子集（有限子集並非可數子集，後者可能有無限多的元素）
• 素數的集合
• 遞歸語言是在形式語言字母表之上所有可能詞的集合中的遞歸集合。

性質

如果$A$是遞歸集合，則$A$的補集是遞歸集合。 如果$A$和$B$是遞歸集合，則$A\cap B$、$A\cup B$和$A\times B$ 是遞歸集合。集合$A$是遞歸集合，當且僅當$A$和$A$的補集是遞歸可枚舉集合。一個遞歸集合在全可計算函數下的原像（preimage）是遞歸集合。

參見

• 遞歸可枚舉集合
• 遞歸函數