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
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
Sources
1. Entscheidungsproblem (Wikipedia)
Such an algorithm was proven to be impossible by Alonzo Church and Alan Turing in 1936View the Source Reader 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.