User:IssaRice/Computability and logic/Entscheidungsproblem

Entscheidungsproblem, also called Hilbert's decision problem is a problem in mathematical logic.

Equivalent formulations

Label	Statement	Notes
In terms of validity	Take as input a sentence of first-order logic, and decide whether it is valid (a.k.a. universally valid, true-in-every-interpretation).
In terms of provability	Take as input a sentence of first-order logic, and decide whether it is provable (using only logical axioms).	By Godel's completeness theorem, validity and provability are equivalent.

See also

• wikipedia:Entscheidungsproblem