判定问题

判定问题   pàn dìng wèn tí

数理逻辑的重要研究内容之一。对一整类命题研究是否存在一个统一的确定的方法,用此方法能经有限步骤判定这类中任何一个命题是否具有某种属性,这样的方法称为“判定法”或“算法”。如果存在算法,就称这类命题是可判定的;否则,是不可判定的。例如,由所有命题“pq互质”pq是任意整数)构成的类是可判定的,*辗转相除法就是符合上述要求的判定这类命题的一种算法。