递归集合

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

相关

  • 语义网络语义网络(英语:Semantic Network)常常用作知识表示的一种形式。它其实是一种有向图;其中,顶点代表的是概念,而边则表示的是这些概念之间的语义关系。语义网络是机读型字典(machine-
  • 泡菜泡菜古称葅(zū),是指为了利于长时间存放而经过发酵的蔬菜。一般来说,只要是纤维丰富的蔬菜或水果,都可以被制成泡菜;像是卷心菜、大白菜、红萝卜、白萝卜、大蒜、青葱、小黄瓜、
  • 科学出版社科学出版社,是一家中华人民共和国出版社。ISBN代码为978-7-03。由前中国科学院编译局与1930年代创建的有较大影响的龙门联合书局合并,于1954年8月成立,是一个历史悠久、力量雄
  • 礼物经济礼物经济(英语:gift economy;礼物文化或礼物交换)是自古以来的自由价值经济学模式。交换过程中,给与者没有任何得到价值回报的要求和预期。与之相反,以物易物或者市场经济是用社会
  • 波斯匿王波斯匿王(梵语:Prasenajit,巴利语:Pasenadi),又译作钵逻犀那恃多王,逻犀那恃多王、啰洗曩喻那王。意译胜军王、胜光王、和悦王、月光王、明光王。古印度憍萨罗国国王,子毘琉璃、祗陀
  • 万丹省万丹省(印尼语:Banten)是印度尼西亚的一个省,位于爪哇岛最西部,隔巽他海峡与苏门答腊岛相望。2000年自西爪哇省分出。面积9,160.7平方公里。首府西冷。下辖三市和四区。2005年人
  • 查理二世查理二世,可能为以下欧洲君主:
  • 持有自动化输出内容的版权原创性门槛(Threshold of originality)是起源于英美法系中的一个著作权法概念,用来检验某一事物是否能得到著作权法的保护。著作权法保护的对象是作品,而不是作品中所包含的概念
  • 奈梅亨拉德伯德大学奈梅亨拉德堡德大学,是一所创建于1923年位于荷兰最古老城市奈梅亨的公立大学。最早的奈梅亨大学创建于1655年,1680年终止。创建于1923年10月17日的奈梅亨拉德堡德大学最初命名
  • 乳杆菌属见内文乳杆菌属(Lactobacillus)即为乳酸杆菌,是一群存在于人类体内的益生菌。乳杆菌因能够将碳水化合物发酵成乳酸而得名,可用于制造液态酸奶、固态奶酪、德国酸菜、啤酒、葡萄