递归集合

维基百科,自由的百科全书
跳转至: 导航搜索

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

定义[编辑]

自然数的子集 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补集是递归集合。 如果AB是递归集合,则ABABA × B 是递归集合。集合A是递归集合,当且仅当AA补集递归可枚举集合。一个递归集合在可计算函数下的原像(preimage)是递归集合。

参见[编辑]