判定问题 decision problem 如何寻找一种方法,去判定某一个事物是否具有某种属性的问题。主要指公式的可证性、普遍有效性和可满足性。在数理逻辑中,一个判定问题有如下的一般形式:给出一个集合A和一性质P,去寻找一个算法,使它能告知对于集合A中的任何元素a(即a∈A),是否具有性质P;或者能证明不可能找到这样的算法。例如:自然数n是偶数吗?这里自然数n组成的集合N,就相当于一般形式中的集合A,“是偶数吗”?相当于性质P。它构成一个判定问题:可以用符号写成: {自然数n是偶数吗?|n∈N} 显然这个判定问题存在一个算法,对于N中的任一个自然n,则只需用2去除。如果余数为0,那么n就是偶数;如果余数为1,n就不是自然数。这一算法适用于一切自然数。给出一个数论谓词(或一个数论关系),或依赖于若干参数的问题类M(x1,…,xn),对任意数a1,…,an∈N,问M(a1,…,an)是否成立或是否真的判定问题又往往可归结为给定N的一个子集A,对任意x∈N,问x是否属于A?如能找到一个机械的方法(或算法),用它可对任意a1,…,an∈N,能在有限步内判定M(a1,…,an)是否成立,或对任意x∈N,能在有限步内判定x是否在A中,则称相应的判定问题是能行可解的。如找不到所要的算法,则称相应的判定问题是能行不可解的。如果使用了丘奇论点,那末判定问题则成为是否能找到某个递归函数的问题,或成为证明某个数论函数是否可计算的问题。令: 或: 若CM(或CA)是一个递归函数(或是可计算的),则称相应的判定问题M(x1,…,xn)(或x∈A?)是递归可解的,或递归可判定的。若CM(或CA)不是一个递归函数(或不可计算),则称相应的判定问题是递归不可解的,或递归不可判定的。再令:  或: 若C瘙櫛M(或C瘙櫛A)是一个递归部分函数(或是可计算的),则称相应的判定问题是半可解的,或是半可判定的。 |