首页 >
递归集合
✍ dations ◷ 2025-11-30 23:59:09 #递归集合
在可计算性理论中,一个自然数的子集被称为递归的、可计算的或具可判定性,如果我们可以构造一个算法,使之能在有限时间内终止并判定一个给定元素是否属于这个集合。更一般的集合的类叫做递归可枚举集合。这些集合包括递归集合,对于这种集合,只需要存在一个算法,当某个元素位于这个集合中时,能够在有限时间内给出正确的判定结果,但是当元素不在这个集合中时,算法可能会永远运行下去(但不会给出错误答案)。自然数的子集 S 被称为递归的,如果存在一个全可计算函数使得换句话说,集合 S 是递归的,当且仅当指示函数
1
S
{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)是递归集合。
相关
- 突变突变(英语:Mutation,即基因突变)在生物学上的含义,是指细胞中的遗传基因(通常指存在于细胞核中的去氧核糖核酸)发生的改变。它包括单个碱基改变所引起的点突变,或多个碱基的缺失、重
- 心肌炎心肌炎(拉丁语:Myocarditis),也称为炎症性心肌病(Inflammatory Cardiomyopathy),是心肌的炎症。症状可表现为呼吸困难、胸口疼痛(英语:chest pain)、运动能力降低、心律不整等。发病时
- 头颈癌头颈癌(Head and Neck Cancers)是指位于头颈部位,除了脑癌以外的其他恶性肿瘤。较常见有口腔癌、鼻咽癌,另外还有口咽癌、下咽癌、喉癌、鼻窦癌、唾液腺癌以及甲状腺癌等。头颈
- 氯胺酮氯胺酮(英语:Ketamine),俗称小姐、K仔、K粉、K他命、克他命、恺他命,在台湾,经常被称为裤子(相对于衣,衣代表的是Ecstasy 的第一个字母)、下面(相对于穿在上面的衣服),一种非鸦片系麻醉
- ICD-9编码列表 (520–579)Template:Developmental tooth disease Template:Acquired tooth disease Template:Dentofacial anomalies and jaw disease Template:Oral pathology
- 组胺组胺(英语:Histamine),是一种有机含氮的环状化合物。它参与局部免疫反应和炎症反应,并具有作为瘙痒介体中心与调节肠道生理功能的作用。它还被用作神经递质。组胺由嗜碱性球和附
- 雷迪帕韦雷迪帕韦(英语:Ledipasvir,亦作GS-5885)是吉利德科学(英语:Gilead Sciences)研发的治疗丙型肝炎的药物。在完成了Ⅲ期临床试验后,吉利德于2014年2月10日向美国联邦政府申请报批了固
- 故意伤害在中华人民共和国法律中,故意伤害罪(英语:intentional assault)是指侵犯或者损害被害人身体的行为。被害人可以是一个健康人也可以是一个本身有疾病的人,而导致病情加重或者死亡
- 温耶温耶是土耳其的城镇,由奥尔杜省负责管辖,位于该国北部,距离首府奥尔杜76公里,面积440平方公里,处于海拔水平面,主要农产品是榛子,2010年人口114,408。
- 胆总管胆管为胆汁由肝脏传送至十二指肠的一个管道。肝内的胆小管逐级合并成左、右肝管,出肝门再合成为肝总管;肝总管与胆囊管汇合成胆总管。肝细胞持续不断的制造胆汁浓缩并储存于胆
