可判定的谓词

也叫能行可判定的谓词或算法可判定的谓词。

严格地讲，在谈论一个谓词是否可判定的时候，要先指定一个计算模型(如图灵机、URM、波斯特系统、马尔科夫算法、等等)。如果谓词P的特征函数C(x，…，x)是该种模型可计算的(如图灵可计算的)，称P为(使用该种模型)可判定的(如图灵可判定的)。由于已知的各种计算模型全都彼此等价，因而实际上可以不必强调是在哪种计算模型下讨论问题，而笼统地称为可判定的谓词。如果P不是可判定的谓词，则称为不可判定的谓词。

一个谓词是可判定的，当且仅当它是递归的。