In mathematics, the Entscheidungsproblem (German for 'decision problem') is a challenge posed by David Hilbert in 1928. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ... David Hilbert (January 23, 1862, Königsberg, East Prussia – February 14, 1943, Göttingen, Germany) was a German mathematician, recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. ...

The Entscheidungsproblem asks for a computer program that will take as input a description of a formal language and a mathematical statement in the language and return as output either "True" or "False" according to whether the statement is true or false. The program need not justify its answer, or provide a proof, so long as it is always correct. Such a computer program would be able to decide, for example, whether statements such as the continuum hypothesis or the Riemann hypothesis are true, even though no proof or disproof of these statements is known. In mathematics, the continuum hypothesis is a hypothesis about the possible sizes of infinite sets. ... Unsolved problems in mathematics: Is the real part of a non-trivial zero of the Riemann zeta function always ½? In mathematics, the Riemann hypothesis (also called the Riemann zeta-hypothesis), first formulated by Bernhard Riemann in 1859, is one of the most famous unsolved problems. ...

In 1936, Alonzo Church and Alan Turing published independent papers showing that it is impossible to decide algorithmically whether statements in arithmetic are true or false, and thus a general solution to the Entscheidungsproblem is impossible. This result is now known as Church's Theorem. Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician who was responsible for some of the foundations of theoretical computer science. ... Alan Mathison Turing, OBE (June 23, 1912 – June 7, 1954), was an English mathematician, logician, and cryptographer. ... Arithmetic or arithmetics (from the Greek word αριθμός = number) is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple daily counting to advanced science and business calculations. ...

History of the problem

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 (Davis 2000:pp. 3–20). He realized that the first step would have to be a clean formal language, and much of his subsequent work was directed towards that goal. In 1928, David Hilbert and Wilhelm Ackermann posed the question in the form outlined above. It has been suggested that this article be split into multiple articles. ... (16th century - 17th century - 18th century - more centuries) As a means of recording the passage of time, the 17th century was that century which lasted from 1601-1700. ... A calculating machine is a machine designed to come up with calculations (i. ... In mathematics, logic, and computer science, a formal language is a set of finite-length words (i. ... Year 1928 (MCMXXVIII) was a leap year starting on Sunday (link will display full calendar). ... David Hilbert (January 23, 1862, Königsberg, East Prussia – February 14, 1943, Göttingen, Germany) was a German mathematician, recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. ... Wilhelm Ackermann (March 29, 1896, Herscheid municipality, Germany – December 24, 1962 Lüdenscheid, Germany ) was a German mathematician best known for the Ackermann function, an important example in the theory of computation. ...

In continuation of his "program" with which he challenged the mathematics community in 1900, at a 1928 international conference David Hilbert asked three questions, the third of which became known as "Hilbert's Entscheidungsproblem" (Hodges p. 91). As late as 1930 he believed that there would be no such thing as an unsolvable problem (Hodges p. 92, quoting from Hilbert).

The negative answer

Before the question could be answered, the notion of "algorithm" had to be formally defined. This was done by Alonzo Church in 1936 with the concept of "effective calculability" based on his λ calculus and by Alan Turing in the same year with his concept of Turing machines. It was later recognized that these are equivalent models of computation. Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician who was responsible for some of the foundations of theoretical computer science. ... The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ... An artistic representation of a Turing Machine . ... An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in Automata theory. ...

The negative answer to the Entscheidungsproblem was then given by Alonzo Church in 1936 and independently shortly thereafter by Alan Turing, also in 1936. Church proved that there is no computable function which decides for two given λ calculus expressions whether they are equivalent or not. He relied heavily on earlier work by Stephen Kleene. Turing reduced the halting problem for Turing machines to the Entscheidungsproblem. The work of both authors was heavily influenced by Kurt Gödel's earlier work on his incompleteness theorem, especially by the method of assigning numbers (a Gödel numbering) to logical formulas in order to reduce logic to arithmetic. Computable functions (or Turing-computable functions) are the basic objects of study in computability theory. ... Stephen Cole Kleene (January 5, 1909 - January 25, 1994) was an American mathematician whose work at the University of Wisconsin-Madison helped lay the foundations for theoretical computer science. ... In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ... [...]I dont believe in natural science. ... In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931. ... This article or section may be confusing or unclear for some readers, and should be edited to rectify this. ...

Turing's argument is the following. Suppose we had a general decision algorithm for statements in a first-order language. The question whether a given Turing machine halts or not can be formulated as a first-order statement, which would then be susceptible to the decision algorithm. But Turing had proven earlier that no general algorithm can decide whether a given Turing machine halts. First-order logic (FOL) is a universal language in symbolic science, and is in use everyday by mathematicians, philosophers, linguists, computer scientists and practitioners of artificial intelligence. ...

The Entscheidungsproblem is related to Hilbert's tenth problem, which asks for an algorithm to decide whether Diophantine equations have a solution. The non-existence of such an algorithm, established by Yuri Matiyasevich in 1970, also implies a negative answer to the Entscheidungsproblem. Hilberts tenth problem is the tenth on the list of Hilberts problems of 1900. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ... In mathematics, a Diophantine equation is a polynomial equation that only allows the variables to be integers. ... Yuri Matiyasevich born March 2, 1947 in Leningrad, is a Russian mathematician. ... 1970 (MCMLXX) was a common year starting on Thursday. ...

Some first-order theories are algorithmically decidable; examples of this include Presburger arithmetic, real closed fields and static type systems of programming languages. The general first-order theory of the natural numbers expressed in Peano's axioms cannot be decided with such an algorithm, however. Presburger arithmetic is the first-order theory of the natural numbers with addition. ... In mathematics, a real closed field is an ordered field F in which any of the following equivalent conditions are true: Every non-negative element of F has a square root in F, and any polynomial of odd degree with coefficients in F has at least one root in F... On computer science, a datatype (often simply type) is a name or label for a set of values and some operations which can be performed on that set of values. ... A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is... In mathematics, the Peano axioms (or Peano postulates) are a set of second-order axioms proposed by Giuseppe Peano which determine the theory of arithmetic. ...

References

• Alonzo Church, "An unsolvable problem of elementary number theory", American Journal of Mathematics, 58 (1936), pp 345 - 363
• Alonzo Church, "A note on the Entscheidungsproblem", Journal of Symbolic Logic, 1 (1936), pp 40 - 41.
• Martin Davis, 2000, Engines of Logic, W.W. Norton & Company, London, ISBN 0-393-32229-7 pbk.
• Alan Turing, "On computable numbers, with an application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230 - 265. Online version. Errata appeared in Series 2, 43 (1937), pp 544 - 546.
• Martin Davis, "The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions", Raven Press, New York, 1965. Turing's paper is #3 in this volume. Papers include those by Godel, Church, Rosser, Kleene, and Post.
• Andrew Hodges, Alan Turing: The Enigma, Simon and Schuster, New York, 1983. Allen M. Turing's biography. Cf Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
• Toulmin, Stephen, "Fall of a Genius", a book review of "Alan Turing: The Enigma by Andrew Hodges", in The New York Review of Books, January 19, 1984, p. 3ff.
• Alfred North Whitehead and Bertrand Russell, Principia Mathematica to *56, Cambridge at the University Press, 1962. Re: the problem of paradoxes, the authors discuss the problem of a set not be an object in any of its "determining functions", in particular "Introduction, Chap. 1 p. 24 "...difficulties which arise in formal logic", and Chap. 2.I. "The Vicious-Circle Principle" p.37ff, and Chap. 2.VIII. "The Contradictions" p.60 ff.

Traditionally, number theory is that branch of pure mathematics concerned with the properties of integers and contains many open problems that are easily understood even by non-mathematicians. ... In mathematics, theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers, are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. ... The London Mathematical Society (LMS) is the leading mathematical society in England. ... Martin Davis, (born 1926, New York City) is an American mathematician, known for his work on Hilberts tenth problem. ... Stephen Edelston Toulmin (born March 25, 1922) is a British philosopher, author, and educator. ... Alfred North Whitehead, OM (February 15, 1861 Ramsgate, Kent, England – December 30, 1947 Cambridge, Massachusetts, USA) was an English-born mathematician who became a philosopher. ... Bertrand Arthur William Russell, 3rd Earl Russell OM FRS (18 May 1872 – 2 February 1970), was a British philosopher, logician, mathematician and advocate for social reform. ...

See also

Look up Entscheidungsproblem in
Wiktionary, the free dictionary.

• Halting Problem
• Hilbert's second problem