递归可枚举集合

✍ dations ◷ 2025-04-03 17:24:19 #递归可枚举集合
递归可枚举集合(英语:Recursively enumerable set)是可计算性理论或更狭义的递归论中的一个概念。可数集合S被称为是递归可枚举、计算可枚举的、半可判定的或可证明的,如果或者等价的说,包含所有可递归枚举集合的复杂性类是 RE。共同的编程意义会暗示出如何转换一种算法到等价的另一种算法。第一种情况说明了为什么有时说半可判定的,而第二种情况说明了为什么叫计算可枚举的。可数集合 S {displaystyle S} 是递归可枚举的,如果存在一个偏可计算函数 f {displaystyle f} 使得换句话说, S {displaystyle S} 是 f {displaystyle f} 的域:(注意这是偏函数的域的两种可能意义之一,是在递归论中所偏好的定义域。参见在偏函数中的讨论。)集合 S {displaystyle S} 被成为 co-递归可枚举的或 co-r.e.,如果 S {displaystyle S} 的补集是递归可枚举的。可数集合 S {displaystyle S} 被叫做递归可枚举的,如果存在着一个偏可计算函数 f :⊆ N → S {displaystyle f:subseteq mathbb {N} to S} ,使得 S {displaystyle S} 是 f {displaystyle f} 的值域:f {displaystyle f} 被称为枚举函数,因为它关联上一个枚举上的次序(rank)到 S {displaystyle S} 的每个元素。因为邱奇-图灵论题声称可计算函数被图灵机和其他计算模型等价的定义,我们陈述定义为这也是递归可枚举集合的常见定义。如果 A 和 B 是递归可枚举集合,则 A ∩ B、A ∪ B 和 A × B 是递归可枚举集合。集合 A 是递归集合,当且仅当 A 和 A 补集二者是递归可枚举集合。递归可枚举集合一个可计算函数下的原像是递归可枚举集合。

相关

  • 醛固酮减少症醛固酮减少症(hypoaldosteronism ),是一种内分泌疾病,病状特征表现为醛固酮激素水平降低。与之类似,单一性低醛固酮症(isolated hypoaldosteronism)是一种醛固酮水平降低,而皮质醇没
  • 人工心脏人工器官(英语:Artificial organs)是用人工材料制成,能部分或全部代替人体自然器官功能的部件。目前,除人工大脑外,几乎人体各个器官都在进行人工模拟研制中。不少人工制造的器官
  • 磷脂双分子层磷脂双分子层(英语:lipid bilayer 或phospholipid bilayer)是由两层磷脂分子组成的薄膜。 几乎所有细胞生物的细胞膜和许多病毒的包膜都主要由磷脂双分子层构成,此外,核被膜和
  • E. J. Corey艾里亚斯·詹姆斯·科里(英语:Elias James Corey,1928年7月12日-),美国有机化学家,有机合成化学领域的一代宗师,也是一个备受争议的人物。1990年诺贝尔化学奖得主,得奖原因是“发展了
  • 火灾暴风火灾暴风(英语:Firestorm),又称火风暴或火灾风暴,是大范围火灾本身所创造和维持的风力系统,是严重野火或山火中的一种自然现象。也会用来描述一般的巨型火灾 ,火灾风暴的确定特征必
  • Pa5f26d17s22,8,18,32,20,9,2主条目:镤的同位素镤(英语:Protactinium,旧译作鎃)是一种放射性化学元素,化学符号为Pa,原子序为91。镤是一种银灰色、密度大的锕系元素,容易与氧、水蒸汽
  • 转化生长因子-β乙型转化生长因子(Transforming Growth Factor Beta, TGF-β)是存在于每个人体内的免疫调节因子,帮助改善过敏体质、调节免疫系统正常发展。TGF-β有三种异构物,其中‘TGF-β2’
  • 兰州大学坐标:36°2′47.8483677402″N 103°51′29.032959938″E / 36.046624546594501°N 103.85806471109389°E / 36.046624546594501; 103.85806471109389兰州大学是中华人民共
  • 斯德哥尔摩大学斯德哥尔摩大学(瑞典语:Stockholms universitet)位于瑞典首都斯德哥尔摩,始建于1878年,是瑞典国立大学。拥有人文、社会科学、法学、自然科学与数理等领域系所,在1960年9月3日国有
  • 阳光太阳光,广义的定义是来自太阳所有频谱的电磁辐射。在地球,阳光显而易见是当太阳在地平线之上,经过地球大气层过滤照射到地球表面的太阳辐射,则称为日光。当太阳辐射没有被云遮蔽