Back مسألة القرار (رياضيات) Arabic Праблема вырашальнасці Byelorussian Entscheidungsproblem Catalan Entscheidungsproblem Czech Entscheidungsproblem English Entscheidungsproblem Spanish Problème de la décision French Entscheidungsproblem Croatian Entscheidungsproblem Italian Entscheidungsproblem Latin
The Entscheidungsproblem (German, "decision problem") is a famous problem of mathematics and computer science. David Hilbert formulated the problem in 1928: Is there an algorithm that will take a formal language, and any logical statement in that language, and that will output "True" or "False", depending on the truth value of the statement? The algorithm does not tell how it reaches the answer, nor prove it, as long as the answer is always correct.
In 1936 and 1937, Alonzo Church and Alan Turing showed independently[1][2] that no algorithm can satisfy the Entscheidungsproblem. That is, they showed that it is impossible for an algorithm to decide whether certain mathematical statements are true or false.
- ↑ Turing, A.M. (12 November 1936). "On Computable Numbers, with an Application to the Entscheidungsproblem" (PDF). Proceedings of the London Mathematical Society. 42 (2). London Mathematical Society: 230–265.
- ↑ Church, Alonzo (April 1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics. 58 (2): 345–363 – via JSTOR.