Lecture
The decision problem (German: Entscheidungsproblem) is a problem in the foundations of mathematics, formulated by David Hilbert in 1928: find an algorithm that takes as input the description of any decision problem (a formal language and a mathematical statement " 
" in that language) and, after a finite number of steps, halts and gives one of two answers, "True!" or "False!", depending on whether the statement " " is true or false. The answer does not need to be justified, but it must be correct.
Such an algorithm could, for example, settle the Goldbach conjecture and the Riemann hypothesis, even though their proofs (and refutations) are still unknown. The undecidability of the decision problem (the undecidability of the set of true formulas of arithmetic) for the language of arithmetic containing "equality", "addition" and "multiplication" is a consequence of the non-arithmeticity of this set. Non-arithmeticity is in turn a consequence of Tarski's theorem on the "inexpressibility of the concept of truth in a language by means of that same language".
In 1936, Alonzo Church and, independently of him, Alan Turing published papers showing that no algorithm exists for determining the truth of statements of arithmetic, and therefore the more general decision problem also has no solution. This result became known as the "Church-Turing theorem".
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 a demand 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, those expressible in the lambda calculus). This assumption is now known as the Church-Turing thesis.
The origins of the Entscheidungsproblem go back to Gottfried Leibniz, who in the seventeenth century, after building a successful mechanical calculating machine, dreamed 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 pure 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 stated above.
In pursuit 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 a paper on special cases of the decision problem, prepared with Paul Bernays.
As late as 1930, Hilbert believed that there was no such thing as an unsolvable problem.
Before the question could be answered, the notion of "algorithm" had to be formally defined. This was done by Alonzo Church in 1935 with the concept of "effective calculability", based on his λ-calculus, and by Alan Turing the following year with his concept of Turing machines. Turing immediately recognized that these are equivalent models of computation.
The negative answer to the Entscheidungsproblem was then given by Alonzo Church in 1935-36 (Church's theorem) and independently, shortly afterwards, by Alan Turing in 1936 (Turing's proof). Church proved that there is no computable function that decides, for two given λ-calculus expressions, whether or not they are equivalent. He relied heavily on earlier work by Stephen Kleene. Turing reduced the question of the existence of an "algorithm" or "general method" able to solve the Entscheidungsproblem to the question of the existence of a "general method" that decides whether any given Turing machine halts or not (the halting problem). If "algorithm" is understood to mean a method that can be represented as a Turing machine, and the answer to the latter question is negative (in general), then the answer to the question of the existence of an algorithm for the Entscheidungsproblem must also be negative (in general). In his 1936 paper, Turing says: "To each computing machine 'it' we assign a formula 'Un(it)' and we show that, if there is a general method for determining whether 'Un(it)' is provable, then there is a general method for determining whether 'it' ever prints 0."
The work of Church and Turing was strongly influenced by the earlier work of Kurt Gödel on his incompleteness theorem, especially by his method of assigning numbers (Gödel numbering) to logical formulas in order to reduce logic to arithmetic.
The Entscheidungsproblem is related to Hilbert's tenth problem, which asks for an algorithm to determine whether Diophantine equations have a solution. The nonexistence of such an algorithm, established by the work of Yuri Matiyasevich, Julia Robinson, Martin Davis and Hilary Putnam, with the final part of the proof in 1970, also implies a negative answer to the Entscheidungsproblem.
Some first-order theories are algorithmically decidable; examples include Presburger arithmetic, real closed fields and the static type systems of many programming languages. However, the general first-order theory of the natural numbers expressed in Peano's axioms cannot be decided by an algorithm.
The availability of practical decision procedures for classes of logical formulas is of considerable interest for program and circuit verification. Purely propositional formulas are usually decided using SAT-solving techniques based on the DPLL algorithm. Conjunctive formulas over linear real or rational arithmetic can be decided using the simplex algorithm, and formulas in linear integer arithmetic (Presburger arithmetic) can be decided using Cooper's algorithm or William Pugh's Omega test. Formulas with negations, conjunctions and disjunctions combine the difficulty of satisfiability testing with the difficulty of deciding conjunctions; these are currently usually decided using SMT-solving techniques, which combine SAT solving with decision procedures for conjunctions and propagation techniques. Real polynomial arithmetic, also known as the theory of real closed fields, is decidable; this is the Tarski-Seidenberg theorem, which has been implemented in computers by means of cylindrical algebraic decomposition.
Comments