判定问题

是否存在一种算法，用于判定一个特定的数学断言是否拥有证明？ 判定问题也被称为 Entscheidungsproblem（这并非巧合，在德语中意为“判定问题”）。

利用图灵机的概念，图灵证明了对于初等数论，答案是否定的。 J. Robinson 和塔斯基证明了对于任意域，判定问题是不可判定的。