User:IssaRice/Computability and logic/Entscheidungsproblem

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

Equivalent formulations

Label	Syntactic or semantic	Statement	Notes
In terms of validity	Semantic	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	Syntactic	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.
In terms of satisfiability	Semantic	Take as input a sentence of first-order logic, and decide whether it is satisfiable.
In terms of semantic implication	Semantic	Take as input a set of sentences $\Gamma$ and a sentence $\phi$ (both of first-order logic), and decide whether $\Gamma$ semantically implies (a.k.a. logically implies) $\phi$ .