判定問題

是否存在一種演算法，用於判定一個特定的數學斷言是否擁有證明？ 判定問題也被稱為 Entscheidungsproblem（這並非巧合，在德語中意為“判定問題”）。

利用圖靈機的概念，圖靈證明了對於初等數論，答案是否定的。 J. Robinson 和塔斯基證明了對於任意域，判定問題是不可判定的。