首页 >
递归可枚举集合
✍ dations ◷ 2025-04-04 05:14:53 #递归可枚举集合
递归可枚举集合(英语: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 补集二者是递归可枚举集合。递归可枚举集合一个可计算函数下的原像是递归可枚举集合。
相关
- 外寄生虫感染外寄生物感染是指主要由外寄生物引起的寄生虫病。外寄生物即暂时或永久寄生于宿主体表的寄生物。例如:治疗外寄生物感染常使用杀外寄生虫药(英语:ectoparasiticide),以杀死外寄生
- 钙离子通道钙通道(英语:Calcium channel,台湾极少数时亦称为钙径)是选择性通透Ca2+的离子通道,有时也是电压依赖性钙通道(VDCC(英语:Voltage-dependent calcium channel))的同义词,而另外一种钙通
- 血管性水肿血管神经性水肿是真皮、皮下组织(英语:subcutaneous tissue)、黏膜的局部肿胀。可发生于面部、舌头、喉、腹部、四肢。常与荨麻疹相关,荨麻疹是皮肤的红肿。 Onset is typically
- 动态心电图动态心电图(英语:Holter monitor,即“霍特监测器”)是一种动态心电图设备,是便携式的心脏监测(英语:cardiac monitoring)设备,可以记录24小时内的心脏电传导系统资讯(一般一次至少会记
- 副伤寒热副伤寒是一种由肠道沙门氏菌引起的疾病,目前已知有三种血清型可造成该疾病。症状与伤寒相当类似,且通常发生于接触细菌后的6至30天。 通常会逐渐地在几天内发展出高烧,其他像是
- 精神药物精神药物(英语:psychoactive drug),又称精神药品(psychopharmaceutical,或psychotropic)。有些精神药品具有医疗和科学价值。一种化学物质的概称,这些物质能够穿越血脑屏障,直接作用
- 安全工程安全工程是一门确保工程系统提供足够安全程度的工程科学。安全工程和系统工程、工业工程及其子领域系统安全工程密切相关。安全工程可确保一个生命关键系统的行为符合需求,甚
- 美国国家科学院期刊《美国国家科学院院刊》(英语:Proceedings of the National Academy of Sciences of the United States of America,通常简称为 PNAS;PNAS USA)是美国国家科学院的官方学术周刊。
- 横结肠横结肠是结肠的一部分,位于腹腔上部,前与升结肠以直角向左侧水平移行,在脾脏下方以直角转弯往下接于降结肠。横结肠前部由大网膜悬挂在胃下,后方则由横结肠系膜与腹后壁相连。
- 意大利语族意大利语族是印欧语系下的一族,属于颚音类语言。由其下的通俗拉丁语衍生出罗曼语族。从原始印欧语到原始意大利语的规则语音变化的部分列表:在个别意大利语的演化中出现了进一