递归可枚举集合

易经学习

天地变化的道理

分类目录

使用率很高网站

文章列表

生活要常常分享

维基百科

您身边百科全书

递归可枚举集合

点击查看词条快照

递归可枚举集合（）是可计算性理论或更狭义的递归论中的一个概念。可数集合"-- "被称为是递归可枚举、计算可枚举的、半可判定的或可证明的，如果 "中的元素时，算法才会中止。或者等价的说，包含所有可递归枚举集合的复杂性类是 RE。共同的编程意义会暗示出如何转换一种算法到等价的另一种算法。第一种情况说明了为什么有时说"半可判定的"，而第二种情况说明了为什么叫"计算可枚举的"。定义. 可数集合 formula_1 是递归可枚举的，如果存在一个偏可计算函数 formula_2 使得 formula_3 换句话说，formula_1 是 formula_2 的域: formula_6 集合 formula_1 被称为 co-递归可枚举的或 co-r.e.，如果 formula_1 的补集是递归可枚举的。等价定义. 可数集合 formula_1 被叫做递归可枚举的，如果存在着一个偏可计算函数 formula_10，使得 formula_1 是 formula_2 的值域: formula_13 formula_2 被称为枚举函数，因为它关联上一个枚举上的次序(rank)到 formula_1 的每个元素。注解. 因为邱奇-图灵论题声称可计算函数被图灵机和其他计算模型等价的定义，我们陈述定义为可数集合 formula_1 被称为递归可枚举的，如果有一个图灵机，在给定 formula_1 的一个元素作为输入的时候，总是停机，并在给定的输入不属于 formula_1 的时候永不停机。这也是递归可枚举集合的常见定义。性质. 如果 "A" 和 "B" 是递归可枚举集合，则 "A" ∩ "B"、"A" ∪ "B" 和 "A" × "B" 是递归可枚举集合。集合 "A" 是递归集合，当且仅当 "A" 和 "A" 补集二者是递归可枚举集合。递归可枚举集合一个可计算函数下的原像是递归可枚举集合。

刘伟强

都城饭店

南浦大桥

第4届世界合唱比赛

新马克思主义

象鼻山路

华俄道胜银行大楼 (汉口)

柯尼卡

宗人府

王宝剑

上海东方汇理银行大楼

华南农业大学