判定问题

一个判定问题涉及两个方面：一个可数无穷的对象集X，有关X的一个性质(或关系)P。所谓判定问题就是要求给出一个能行过程(算法)，以在有穷的步骤之内确定X中的任何一个(或几个)对象是否具有性质(或关系)P。如果给出了这样的能行过程，就称该判定问题是可解的(或该问题是可判定的)；如果这样的能行过程不存在，就称该判定问题是不可解的(或该问题是不可判定的)。

对于建立在可数语言之上的一阶形式理论(形式系统)，确定“任何一个公式是否是该理论(该系统)的定理”这样一个判定问题称为该理论(该系统)的判定问题，如果这个判定问题可解，就称该理论(该系统)是可判定的，否则称为不可判定的。

判定问题被认为是数理逻辑的基本问题之一。

对于非自然数的对象集X，可以通过哥德尔配数法与自然数(的一个子集)建立能行的一一对应，从而X上的性质(或关系)P也就对应一个数论谓词，因而，说一个问题P是可判定的，也就是说是递归谓词。(参见可判定的问题和不可判定的问题。)