遞迴集合

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

定義

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

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 是遞迴的，若且唯若指示函數 $1_{S}$ 是可計算的。

例子

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

性質

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

參見