判定问题

　　判定问题（decision problem），判断是否有一种能够解决某一类问题的能行算法的研究课题。这里所说的一类问题，是指有无穷多个同一类型问题组成的问题。问题的解是指判断这一类问题中的每一个是否具有某种性质，或判断它们中的每一个是真还是假。如果能找到一种有效的能行的算法，依据这种算法，一类问题中的每一个都可以有确定解，就称这一类问题是可判定的；否则就称这一类问题是不可判定的。一般说来，证明一类问题是可判定的比较容易，只要找出解这类问题的一种算法，但要证明一类问题是不可判定的就不容易。要证明任何一种算法都不能判定某一类问题，首先必须给算法下一个严格的精确的定义。这就要用到递归函数和递归论的方法，用递归论的方法可以把一类问题能行地化为自然数集的某个子集。判定这一类问题就变为判定这个子集是否为递归集。如果这一子集不是递归集，则这一类问题就是不可判定的。利用递归论方法，许多问题被证明是不可判定的。例如群的子问题，丢番图方程解的问题，一阶逻辑公式的可满足性问题都被证明是不可判定的。已知一些可判定的和不可判定的问题后，归约的方法就是判定问题的一种重要而有效的方法了。把未知的一类问题的解化归到一类已知的问题的解就是归约方法。如果T，T’是两类问题，T’中的每个问题的解都能化归到T中某个问题的解，就记作T’≤T。这时如果T是可判定的，T’也是可判定的；如果T’是不可判定的，T也是不可判定的。