The Entscheidungsproblem, German for decision problem, is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928 asking for an algorithm that takes a logical statement as input and answers yes or no according to whether the statement is universally valid, that is, valid in every structure. In 1936 Alonzo Church and Alan Turing independently proved that no such algorithm can exist, showing the Entscheidungsproblem is unsolvable in general. The two proofs, developed through Church's lambda calculus and Turing's abstract machines, are foundational results in mathematical logic and the theory of computation. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Classification
Statement Form Connections
Has Statement Form
In Branch
Source Entscheidungsproblem (Wikipedia)
Proved By
Source Entscheidungsproblem (Wikipedia)
Source Entscheidungsproblem (Wikipedia)
Sources
1. Entscheidungsproblem (Wikipedia)
- Such an algorithm was proven to be impossible by Alonzo Church and Alan Turing in 1936
Proved By: David Hilbert, Lead sentence, attribution
posed by David Hilbert and Wilhelm Ackermann in 1928
Proved By: Wilhelm Ackermann, Lead sentence, attribution
posed by David Hilbert and Wilhelm Ackermann in 1928
In Group: Computability and Complexity Theory, Lead section
computer science, the Entscheidungsproblem (German for 'decision problem'; pronounced [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm]) is a challenge
In Branch: Logic and Foundations, Lead section
computer science, the Entscheidungsproblem (German for 'decision problem'; pronounced [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm]) is a challenge
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.