Entscheidungsproblem

In mathematics and computer science, the Entscheidungsproblem; ɛntˈʃaɪ̯dʊŋspʁoˌbleːm) is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. The problem asks for an algorithm that considers, as input, a statement and answers "yes" or "no" according to whether the statement is universally valid, i.e., valid in every structure satisfying the axioms. By the completeness theorem of first-order logic, a statement is universally valid if and only if it can be deduced from the axioms, so the Entscheidungsproblem can also be viewed as asking for an algorithm to decide whether a given statement is provable from the axioms using the rules of logic. In 1936, Alonzo Church and Alan Turing published independent papers showing that a general solution to the Entscheidungsproblem is impossible, assuming that the intuitive notion of "effectively calculable" is captured by the functions computable by a Turing machine (or equivalently, by those expressible in the lambda calculus). This assumption is now known as the Church–Turing thesis. The origin of the Entscheidungsproblem goes back to Gottfried Leibniz, who in the seventeenth century, after having constructed a successful mechanical calculating machine, dreamt of building a machine that could manipulate symbols in order to determine the truth values of mathematical statements. He realized that the first step would have to be a clean formal language, and much of his subsequent work was directed toward that goal. In 1928, David Hilbert and Wilhelm Ackermann posed the question in the form outlined above. In continuation of his "program", Hilbert posed three questions at an international conference in 1928, the third of which became known as "Hilbert's Entscheidungsproblem". In 1929, Moses Schönfinkel published one paper on special cases of the decision problem, that was prepared by Paul Bernays. As late as 1930, Hilbert believed that there would be no such thing as an unsolvable problem. Before the question could be answered, the notion of "algorithm" had to be formally defined.