Entscheidungsproblem

The Entscheidungsproblem, German for decision problem, is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928 asking for an algorithm that takes a logical statement as input and answers yes or no according to whether the statement is universally valid, that is, valid in every structure. In 1936 Alonzo Church and Alan Turing independently proved that no such algorithm can exist, showing the Entscheidungsproblem is unsolvable in general. The two proofs, developed through Church's lambda calculus and Turing's abstract machines, are foundational results in mathematical logic and the theory of computation. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/