万维百科

递归集合

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

定义

自然数的子集 S 被称为递归的,如果存在一个可计算函数

使得

换句话说,集合 S 是递归的,当且仅当指示函数 可计算的

例子

性质

如果是递归集合,则补集是递归集合。 如果是递归集合,则 是递归集合。集合是递归集合,当且仅当补集递归可枚举集合。一个递归集合在可计算函数下的原像(preimage)是递归集合。

参见


本页面最后更新于2021-08-20 16:51,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器