- http://snarc.ia.ac.cn/ren/html/y2010/189.html
- http://baike.baidu.com/view/117790.htm
- http://zh.wikipedia.org/wiki/%E9%80%92%E5%BD%92%E9%9B%86
- 一、
- 在可计算性理论中，一个自然数的子集被称为递归的、可计算的或具可判定性，如果我们可以构造一个算法，使之能在有限时间内终止并判定一个给定元素是否属于这个集合。更一般的集合的类叫做递归可枚举集合。这些集合包括递归集合，对于这种集合，只需要存在一个算法，当某个元素位于这个集合中时，能够在有限时间内给出正确的判定结果，但是当元素不在这个集合中时，算法可能会永远运行下去（但不会给出错误答案）。
- 1、可数集合: 可以与正整数集建立一一对应的无穷集合.
- 2、递归可枚举集合: 可数集合S被称为递归可枚举的, 如果存在生成S的元素的算法. 等价定义:可数集合S被称为递归可枚举的, 如果有一个图灵机, 在给定S的一个元素作为输入的时候总是停机, 并在给定的输入不属于S的时候永不停机.
- 3、递归集合: 可数集合S被称为递归的, 如果存在能够在有限步骤内判定任意给定元素是否属于S的算法.
- 递归集合
性质：
如果 A 是递归集合，则 A 的补集是递归集合。 如果 A 和 B 是递归集合，则 A ∩ B、A ∪ B 和 A × B 是递归集合。集合 A 是递归集合，当且仅当 A 和 A 的补集是递归可枚举集合。一个递归集合在全可计算函数下的原像(preimage)是递归集合。
二、可判定性和半可判定性
判定问题是无穷多个同类个别问题的总称。例如，2是不是素数？6是不是素数？这些都是个别问题，把这类个别问题概括起来，就得到一个判定问题：任意给定的正整数是不是素数？这里的正整数集合称为该判定问题的域，给定域中的一个元素，判定问题就对应一个个别问题。对于一个判定问题，如果能够编出一个程序，以域中任意元素作为输入，执行该程序就能给出相应的个别问题的答案，就称该判定问题为可判定的。例如，“任意正整数是不是素数”这个问题就是可判定的。对于集合A，域中任意元素是否属于它的问题称为集合 A对应的判定问题。集合是递归集的充分必要条件为对应的判定问题是可判定的。因此，全体素数的集合是递归集。
对于一个判定问题，如果能够编出一个程序P，以域中任意元素作为输入，当相应的个别问题的解答是肯定的时候，P的执行将终止并输出“是”，否则P的执行不终止，就称该判定问题为半可判定的。可判定的问题总是半可判定的。集合是递归可枚举集的充分必要条件为对应的判定问题是半可判定的。
图灵在1936年证明，图灵机的停机问题是不可判定的，即不存在一个图灵机能够判定任意图灵机对于任意输入是否停机。图灵机的停机问题是半可判定的。图灵机的停机问题是很重要的，由它可以推出计算机科学、数学、逻辑学中的许多问题是不可判定的。