首页 >
递归可枚举集合
✍ dations ◷ 2025-06-06 16:11:42 #递归可枚举集合
递归可枚举集合(英语: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 补集二者是递归可枚举集合。递归可枚举集合一个可计算函数下的原像是递归可枚举集合。
相关
- 乳制品奶制品,奶类制品的简称,亦称乳制品、乳类食品或奶食品,以奶为基本原料加工而成的食品。除各种直接使用奶制成的饮料外还包括通过发酵获得的食品(奶酪和奶油)以及对奶进行干燥或者
- 发展援助发展援助(Development aid)指以促进发展中国家的发展为目的的国际间实物资源或资金转移。一般是由发达国家提供各种援助资源。
- 腹膜炎腹膜炎,是指一种发生于腹膜的炎症反应。该反应主要由细菌感染、化学物质、物理性伤害等因素引起,且很可能因没有及时治疗而危及生命。其症状可能包含剧烈疼痛、腹部肿胀、发烧
- 利奈唑胺利奈唑胺(Linezolid)为一种人工合成的唑烷酮类抗细菌药,由Pharmacia和Upjohn公司开发,用于治疗对其它几种抗生素有抗性的革兰氏阳性菌所造成的严重感染。利奈唑胺对大多数引起疾
- 菌丝菌丝(英语:hypha pl: hyphae)是丝状真菌(英语:filamentous fungus)或称霉菌(英语:mold)中的一种长、支链丝状结构,它是大多数真菌的结构单位,而部分原核生物如放线菌同样存在菌丝
- 生态平衡生态平衡指的是一段长时间内在一个生态系统里面个体,物种和小生境的数目恒定或者是以某一个值作小幅度震动。正是有这样的震动,人们将这种平衡称作生态平衡。生态系统发展到成
- 肾生理学肾生理学(renal physiology、拉丁语:rēnēs、"肾")为肾的生理学研究。这包括肾脏的所有的功能,包括葡萄糖、氨基酸,及其它小分子的再吸收;钠、钾及其它电解质的调节;体液平衡(Flui
- 受精受精也称作配子结合或受胎,指来自同一物种的生殖细胞(配子)结合并形成新生物个体的过程。对动物来说,这个过程是由精子及卵子融合,最后发育形成胚胎。依照不同的动物物种,受精可以
- 胡斯战争胡斯战争(Hussite Wars)-亦称波希米亚战争 (Bohemian Wars),发生于1419年7月30日至1434年5月30日,起因于神圣罗马帝国领地波希米亚的宗教改革家扬·胡斯在康士坦斯大公会议中,被罗马
- 理论语言学理论语言学(theoretical linguistics)是语言学的分支,用于考察人类语言的共同规律和普遍特征。理论语言学探索语言的本质,设法回答一些有关语言的根本问题,像是:什么是语言?语言是