判定问题

出处：按学科分类—语言、文字 上海辞书出版社《辞海：1999年缩印本(音序)3》第1595页（176字）

数理逻辑的重要研究内容之一。

对一整类命题研究是否存在一个统一的确定的方法，用此方法能经有限步骤判定这类中任何一个命题是否具有某种属性，这样的方法称为“判定法”或“算法”。如果存在算法，就称这类命题是可判定的；否则，是不可判定的。例如，由所有命题“p和q互质”（p、q是任意整数）构成的类是可判定的，*辗转相除法就是符合上述要求的判定这类命题的一种算法。