递归集合, 在可计算性理论中, 一个自然数的子集被称为递归的, 可计算的或具可判定性, 如果我们可以构造一个算法, 使之能在有限时间内终止并判定一个给定元素是否属于这个集合, 更一般的集合的类叫做递归可枚举集合, 这些集合包括, 对于这种集合, 只需要存在一个算法, 当某个元素位于这个集合中时, 能够在有限时间内给出正确的判定结果, 但是当元素不在这个集合中时, 算法可能会永远运行下去, 但不会给出错误答案, 目录, 定义, 例子, 性质, 参见定义, 编辑自然数的子集, 被称为递归的, 如果存在一个全可计算函数,. 在可计算性理论中 一个自然数的子集被称为递归的 可计算的或具可判定性 如果我们可以构造一个算法 使之能在有限时间内终止并判定一个给定元素是否属于这个集合 更一般的集合的类叫做递归可枚举集合 这些集合包括递归集合 对于这种集合 只需要存在一个算法 当某个元素位于这个集合中时 能够在有限时间内给出正确的判定结果 但是当元素不在这个集合中时 算法可能会永远运行下去 但不会给出错误答案 目录 1 定义 2 例子 3 性质 4 参见定义 编辑自然数的子集 S 被称为递归的 如果存在一个全可计算函数 f S N displaystyle f S to mathbb N nbsp 使得 f x 0 if x S 0 if x S displaystyle f x left begin matrix 0 amp mbox if x in S neq 0 amp mbox if x notin S end matrix right nbsp 换句话说 集合 S 是递归的 当且仅当指示函数 1 S displaystyle 1 S nbsp 是可计算的 例子 编辑空集 自然数 自然数的所有有限子集 有限子集并非可数子集 后者可能有无限多的元素 素数的集合 递归语言是在形式语言字母表之上所有可能词的集合中的递归集合 性质 编辑如果A displaystyle A nbsp 是递归集合 则A displaystyle A nbsp 的补集是递归集合 如果A displaystyle A nbsp 和B displaystyle B nbsp 是递归集合 则A B displaystyle A cap B nbsp A B displaystyle A cup B nbsp 和A B displaystyle A times B nbsp 是递归集合 集合A displaystyle A nbsp 是递归集合 当且仅当A displaystyle A nbsp 和A displaystyle A nbsp 的补集是递归可枚举集合 一个递归集合在全可计算函数下的原像 preimage 是递归集合 参见 编辑递归可枚举集合 递归函数 取自 https zh wikipedia org w index php title 递归集合 amp oldid 54583787, 维基百科,wiki,书籍,书籍,图书馆,