递归集合

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

相关

  • 肌中央轴空病肌中央轴空病(central core disease (CCD)、central core myopathy)是一种遗传病,其会导致先天性肌肉病变,病理学上肌肉纤维中可发现有肌原纤维(英语:Myofibril)结构破坏的组成。
  • 压强压强,是作用在与物体表面垂直方向上的每单位面积的力(Force)的大小,即是分布在特定作用面上之力与该面积的比值。压强可用任意之力单位与面积单位进行测量,压强的国际标准单位为
  • 选择性配对选型交配(英文:Assortative mating)是交配行为模式的一种,即为选择和自己相近的配偶行进行繁殖,近亲交配是其中一种特殊情况。选型交配可以根据体型大小、颜色、年龄等。产生选型
  • 叶卡捷琳堡叶卡捷琳堡(俄语:Екатеринбу́рг),亦称凯瑟琳堡,曾称斯维尔德洛夫斯克(Свердло́вск),位于乌拉尔山脉东麓,伊塞特河由西北向东南穿城而过。叶卡捷琳堡是俄罗斯
  • 原子序数原子序数(英语:Atomic Number)是一个原子核内质子的数量,因此也称质子数,也等于原子电中性时的核外电子数。拥有同一原子序的原子属于同一化学元素。原子序数的符号是Z。通常原子
  • 说话说话是人类透过口语来沟通的方式,是建基于词法和名称的句法组合是造出极大量的词汇(多数超过一万组),人类所说话的每个词语都是拼音系统中由声母、韵母和声调产生而成,亦可以说是
  • 孤立语孤立语(Isolating language),是有低语素单词比(morpheme-per-word ratio)的语言。依照语言学家的定义分类标准不同,孤立语与分析语之间的关系可能会产生三种情况:相对于综合语(其中
  • 有的语言中,名词、代词、形容词、动词有数的范畴。大部分区分数的语言中,一般只有单数和复数,而一些语言中亦有双数(例如阿拉伯语和古希腊语等)、三数(例如多罗马科语)、微数(Paucal
  • 排遗排遗是生物体将食物经口进入如胃、小肠等消化器官消化吸收后,排除不能消化的剩余废物的过程,如排便等。排泄的关键词是代谢后的废物或其它产物的排出,指的是经过体内生化反应后
  • 二合字母二合字母(digraph、或称二重音字、二重字),在字母系统上是由2个字母组合成的语音,而组成的语音与个别字母的发音不同。且能由二合字母表记出新的语音(音位)。在一些发音变化的场合