Decidability & the Limits of Logic
Gödel, Church–Turing and what no reasoner can do.
In 1928 Hilbert and Ackermann asked for an algorithm that decides whether any given first-order sentence is valid. Within eight years Gödel, Church and Turing had settled how much of that hope survives: every valid sentence has a proof that a machine can find, but no machine can tell you when to stop looking, and no consistent, effectively axiomatized theory captures all of arithmetic.
What you’ll learn
- State Gödel's completeness and compactness theorems, and derive the semi-decidability of first-order validity.
- Sketch the Church–Turing proof that validity is undecidable, by reduction from the halting problem.
- Identify decidable fragments and theories (monadic, two-variable, guarded, Presburger, real closed fields) and their costs.
- State Gödel's incompleteness theorems with their exact hypotheses, and correct common misreadings.
- Explain what these limits imply for automated reasoners and AI systems.
Completeness: proofs exist
Proofs are finite strings over a countable alphabet, and checking whether a string is a proof of from a decidable set is mechanical:
Enumerate all strings and halt with "yes" as soon as one is a proof of :
By completeness, if a proof exists and the search halts; if not, it runs forever. So validity, and entailment from a decidable , is recursively enumerable (); dually, satisfiability of a sentence is co-r.e.
Compactness constrains what first-order logic can say. If a theory has arbitrarily large finite models, it has an infinite one: add the sentences "there are at least elements" for every ; each finite subset is satisfiable, so the whole set is. Hence no first-order theory has exactly the finite structures as its models, and graph connectivity is not first-order definable. Expressive power and good proof theory pull in opposite directions.
Undecidability: no algorithm says no
Given a Turing machine , build a finite set of sentences describing its run on the empty tape: a constant and a successor function for time steps and tape cells; predicates (state at time ), (head at cell ) and (symbol in cell ); axioms for the initial configuration; and one axiom per transition, plus frame axioms, saying how configuration determines configuration .
If halts after steps, applications of the transition axioms derive the halting configuration, so . If never halts, the intended structure (domain , the true run) satisfies but not :
So computably reduces the halting problem to validity. A decision procedure for validity would decide halting, which Turing's diagonal argument rules out. ∎
Two refinements sharpen the picture. Trakhtenbrot (1950) showed that validity over finite structures is not even recursively enumerable, so completeness has no finite-model analogue, which matters for databases, whose structures are finite. And in practice a complete prover may run forever on a non-theorem, so a timeout is not a "no". Finite-model finders can certify some non-theorems by exhibiting a countermodel, but not all: some satisfiable sentences have only infinite models.
Islands of decidability
| Fragment or theory | Decidable? | Complexity |
|---|---|---|
| Propositional logic | yes | SAT NP-complete; validity coNP-complete |
| Monadic first-order logic: unary predicates, no functions (Löwenheim, 1915) | yes | satisfiability NEXPTIME-complete |
| Bernays–Schönfinkel class: prefix , no functions | yes | satisfiability NEXPTIME-complete |
| Two-variable fragment (Mortimer, 1975) | yes, with the finite-model property | NEXPTIME-complete (Grädel, Kolaitis & Vardi, 1997) |
| Guarded fragment (Andréka, van Benthem & Németi, 1998) | yes | 2EXPTIME-complete (Grädel, 1999) |
| Presburger arithmetic (Presburger, 1929) | yes | every decision procedure needs time in the worst case (Fischer & Rabin, 1974) |
| Real closed fields (Tarski, 1951) | yes, by quantifier elimination | doubly exponential in general |
| Full first-order logic; arithmetic | no | validity is r.e.; arithmetic truth is not even arithmetically definable (Tarski) |
The reasons for decidability vary: a bounded or finite model property (monadic, Bernays–Schönfinkel, ), tree-like models that automata can check (guarded fragments, description logics), or quantifier elimination (Presburger arithmetic, real closed fields). The last two rows make a striking contrast: the real numbers with and are decidable, the natural numbers with the same operations are not, and by Matiyasevich's theorem (1970) even the solvability of a single Diophantine equation is undecidable.
Which of these is decidable?
- The first-order theory of
- Whether a polynomial equation with integer coefficients has an integer solution
- The first-order theory of
- Validity of first-order sentences over a single binary predicate
Show the answer
C. The first-order theory of
Tarski showed that real closed fields admit quantifier elimination, so every sentence reduces to a quantifier-free one that can be evaluated. Over the naturals or integers, multiplication brings in the undecidability of Gödel, Church and Matiyasevich.
Incompleteness: truth outruns proof
Arithmetization. Code formulas and proofs as numbers . The relation " codes a -proof of the formula coded by " is decidable, hence represented in by a formula :
Diagonal lemma. For every formula there is a sentence with . Applied to it gives a sentence that says "I am not provable":
If , some number codes the proof, and verifies the true numerical fact , so ; with the diagonal sentence, as well, contradicting consistency. So , which makes true in , since that is exactly what it says:
If , then although no number codes a proof: an -inconsistency, excluded by Gödel's hypothesis. Rosser's sentence, "for every proof of me there is a shorter proof of my negation", needs only consistency. For the second theorem, can formalize the previous step and prove , so would give . ∎
What it means for AI
- Provers are semi-decision procedures. A first-order prover can confirm theorems but cannot always refute non-theorems, so practical systems combine saturation with timeouts, finite-model finders and decidable fragments.
- Knowledge representation trades expressiveness for guarantees. Ontology languages are built on decidable description logics, and Datalog drops function symbols, precisely so that reasoning always terminates.
- Verification is undecidable in general. By Rice's theorem every non-trivial semantic property of programs is undecidable, so verifiers are sound but incomplete, rely on human-supplied invariants, or restrict the programs they accept.
- No architecture escapes. These are limits on what any algorithm can compute, symbolic or neural. A learned model that answers arbitrary validity questions must sometimes be wrong or decline to answer; what learning can change is which problems get solved in practice.
Key takeaways
- Completeness (Gödel, 1929): iff . With compactness and Löwenheim–Skolem, it shapes what first-order logic can express.
- Enumerating proofs makes validity semi-decidable, and the Church–Turing reduction from the halting problem makes it undecidable: a prover may never say no.
- Decidable islands exist (monadic, Bernays–Schönfinkel, two-variable, guarded, Presburger, real closed fields), often at doubly exponential cost or worse.
- Incompleteness (Gödel, 1931; Rosser, 1936): every consistent, effectively axiomatized theory interpreting leaves some sentence undecided and cannot prove its own consistency.
- These limits bind every algorithm, symbolic or learned; practical systems answer with decidable fragments, timeouts, model finders and machine-checkable proofs.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Which hypotheses does the Gödel–Rosser first incompleteness theorem require of a theory ?
- is complete and decidable
- is consistent, effectively axiomatized and interprets Robinson arithmetic
- is first-order and has an infinite model
- contains set theory
Show the answer
B. is consistent, effectively axiomatized and interprets Robinson arithmetic
Drop any hypothesis and the conclusion can fail: an inconsistent theory proves everything, true arithmetic is complete but not effectively axiomatized, and Presburger arithmetic is complete because it cannot interpret .
First-order logic is complete (Gödel, 1929), yet Peano arithmetic is incomplete (Gödel, 1931). How can both hold?
- The 1931 theorem refuted the 1929 one
- Peano arithmetic is not a first-order theory
- Completeness applies only to finite models
- Completeness says that sentences true in every model of are provable; is true in but false in some nonstandard model, so it is not a consequence of
Show the answer
D. Completeness says that sentences true in every model of are provable; is true in but false in some nonstandard model, so it is not a consequence of
The theorems concern different notions: consequence over all models versus truth in the intended model. Since , completeness guarantees a model of , necessarily nonstandard.
Which set is recursively enumerable but not decidable?
- The satisfiable first-order sentences
- The valid propositional sentences
- The sentences true in
- The valid first-order sentences
Show the answer
D. The valid first-order sentences
Enumerating proofs lists the valid sentences (by completeness), and Church and Turing showed that no algorithm decides membership.
Presburger arithmetic is decidable. What is known about its complexity?
- It is decidable in polynomial time
- Every decision procedure needs doubly exponential time in the worst case (Fischer & Rabin, 1974)
- It is decidable only for quantifier-free sentences
- Nothing: its complexity is unknown
Show the answer
B. Every decision procedure needs doubly exponential time in the worst case (Fischer & Rabin, 1974)
Fischer and Rabin proved a lower bound for some constant , and quantifier elimination gives a triply exponential upper bound. Decidable does not mean feasible.
Further reading
- K. Gödel, "Die Vollständigkeit der Axiome des logischen Funktionenkalküls," Monatshefte für Mathematik und Physik 37 (1930), 349–360; and "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I," Monatshefte für Mathematik und Physik 38 (1931), 173–198.
- A. Church, "A note on the Entscheidungsproblem," Journal of Symbolic Logic 1(1) (1936), 40–41.
- A. M. Turing, "On computable numbers, with an application to the Entscheidungsproblem," Proceedings of the London Mathematical Society s2-42 (1936), 230–265.
- E. Börger, E. Grädel & Y. Gurevich, The Classical Decision Problem (Springer, 1997).
- P. Smith, An Introduction to Gödel's Theorems, 2nd ed. (Cambridge University Press, 2013).