遞歸集合

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

定義

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

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

使得

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

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

例子

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

性質

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

參見

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