User:IssaRice/Computability and logic/Entscheidungsproblem: Difference between revisions
(Created page with "'''Entscheidungsproblem''', also called '''Hilbert's decision problem''' is a problem in mathematical logic. ==Equivalent formulations== {| class="wikitable" |} ==See also=...") |
|||
| Line 4: | Line 4: | ||
{| class="wikitable" | {| class="wikitable" | ||
|- | |||
! 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. | |||
|} | |} | ||
Revision as of 00:36, 9 February 2019
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. |