Entscheidungsproblem
Sign in to saveIn mathematics and computer science, the ; ) is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. It asks for an algorithm that considers an inputted statement and answers "yes" or "no" according to whether it is universally valid, i.e., valid in every structure. Such an algorithm was proven to be impossible by Alonzo Church and Alan Turing in 1936.
~13 min read
Article
13 sectionsContents
- Completeness theorem
- History
- Negative answer<!--'Church's theorem' redirects here-->
- Generalizations
- Fragments
- Aristotelian and relational
- Arity
- Quantifier prefix
- Practical decision procedures
- See also
- Notes
- References
- External links
In mathematics and computer science, the ; ) is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. It asks for an algorithm that considers an inputted statement and answers "yes" or "no" according to whether it is universally valid, i.e., valid in every structure. Such an algorithm was proven to be impossible by Alonzo Church and Alan Turing in 1936.
==Completeness theorem== By the completeness theorem of first-order logic, a statement is universally valid if and only if it can be deduced using logical rules and axioms, so the ' can also be viewed as asking for an algorithm to decide whether a given statement is provable using the rules of logic.