查看“︁递归集合”︁的源代码

{{NoteTA
|G1 = IT
|G2 = Math
}}
在[[可计算性理论]]中，一个[[可数集合|自然数的子集]]被称为'''递归的'''、'''可计算的'''或具[[可判定性]]，如果我们可以构造一个[[算法]]，使之能在有限时间内终止并判定一个给定元素是否属于这个集合。更一般的集合的类叫做[[递归可枚举集合]]。这些集合包括'''递归集合'''，对于这种集合，只需要存在一个算法，当某个元素位于这个集合中时，能够在有限时间内给出正确的判定结果，但是当元素不在这个集合中时，算法可能会永远运行下去（但不会给出错误答案）。

==定义==
[[自然数]]的子集 ''S'' 被称为'''递归的'''，如果存在一个[[全函数|全]][[可计算函数]]
:<math>f:S \to \mathbb{N}</math>
使得
:<math>f(x) = 
\left\{\begin{matrix} 
0 &\mbox{if}\ x \in S \\
\neq 0 &\mbox{if}\ x \notin S
\end{matrix}\right.
</math>

换句话说，集合 ''S'' 是递归的，[[当且仅当]][[指示函数]] <math>1_{S}</math> 是[[可计算函数|可计算的]]。

==例子==
* [[空集]] 
* 自然数
* 自然数的所有[[有限集合|有限子集]]（有限子集并非[[可数集|可数子集]]，后者可能有无限多的元素）
* [[素数]]的集合
* [[递归语言]]是在[[形式语言]][[字母表 (计算机科学)|字母表]]之上所有可能词的集合中的递归集合。

==性质==
如果<math>A</math>是递归集合，则<math>A</math>的[[补集]]是递归集合。
如果<math>A</math>和<math>B</math>是递归集合，则<math>A\cap B</math>、<math>A\cup B</math>和<math>A \times B</math> 是递归集合。集合<math>A</math>是递归集合，[[当且仅当]]<math>A</math>和<math>A</math>的[[补集]]是[[递归可枚举集合]]。一个递归集合在[[全函数|全]][[可计算函数]]下的[[原像]]（preimage）是递归集合。

==参见==
* [[递归可枚举集合]]
* [[递归函数]]

[[Category:递归论]]
[[Category:計算理論]]

{{集合论}}