Entscheidungsproblem facts for kids
The Entscheidungsproblem (German, "decision problem") is a famous problem of mathematics. David Hilbert formulated the problem in 1928: Is there an algorithm that will take a formal language, and a 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, that there can be no answer to the Entscheidungsproblem. They showed that it is impossible for an algorithm to decide whether statements in arithmetic are true or false. For this reason, there can be no solution for the Entscheidungsproblem . This was proven by Alan Turings "Turing Machine" which was created in the 1930s.
See also
In Spanish: Entscheidungsproblem para niños
