递归集合
在可计算性理论中,一个自然数的子集被称为递归的、可计算的或具可判定性,如果我们可以构造一个算法,使之能在有限时间内终止并判定一个给定元素是否属于这个集合。更一般的集合的类叫做递归可枚举集合。这些集合包括递归集合,对于这种集合,只需要存在一个算法,当某个元素位于这个集合中时,能够在有限时间内给出正确的判定结果,但是当元素不在这个集合中时,算法可能会永远运行下去(但不会给出错误答案)。
目录
1 定义
2 例子
3 性质
4 参见
定义
自然数的子集 S 被称为递归的,如果存在一个全可计算函数
- f:S→N{displaystyle f:Sto mathbb {N} }
使得
- f(x)={0if x∈S≠0if x∉S{displaystyle f(x)=left{{begin{matrix}0&{mbox{if}} xin S\neq 0&{mbox{if}} xnotin Send{matrix}}right.}
换句话说,集合 S 是递归的,当且仅当指示函数 1S{displaystyle 1_{S}} 是可计算的。
例子
- 空集
- 自然数
- 自然数的所有有限子集(有限子集并非可数子集,后者可能有无限多的元素)
素数的集合
递归语言是在形式语言字母表之上所有可能词的集合中的递归集合。
性质
如果A{displaystyle A}是递归集合,则A{displaystyle A}的补集是递归集合。
如果A{displaystyle A}和B{displaystyle B}是递归集合,则A∩B{displaystyle Acap B}、A∪B{displaystyle Acup B}和A×B{displaystyle Atimes B} 是递归集合。集合A{displaystyle A}是递归集合,当且仅当A{displaystyle A}和A{displaystyle A}的补集是递归可枚举集合。一个递归集合在全可计算函数下的原像(preimage)是递归集合。
参见
- 递归可枚举集合
- 递归函数
|