Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

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

DerivationValidity is semi-decidable
  1. ProofΓ(π,φ)  is decidable\mathrm{Proof}_\Gamma(\pi,\varphi)\ \ \text{is decidable}

    Proofs are finite strings over a countable alphabet, and checking whether a string is a proof of φ\varphi from a decidable set Γ\Gamma is mechanical:

  2. for k=1,2,3,⋯:  if ProofΓ(πk,φ) then halt\text{for } k=1,2,3,\dots:\ \ \text{if } \mathrm{Proof}_\Gamma(\pi_k,\varphi) \text{ then halt}

    Enumerate all strings π1,π2,…\pi_1,\pi_2,\dots and halt with "yes" as soon as one is a proof of φ\varphi:

  3. {φ: ⊨φ} ∈ Σ10\{\varphi:\ \models\varphi\}\ \in\ \Sigma^0_1

    By completeness, if Γ⊨φ\Gamma\models\varphi a proof exists and the search halts; if not, it runs forever. So validity, and entailment from a decidable Γ\Gamma, is recursively enumerable (Σ10\Sigma^0_1); 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 nn elements" for every nn; 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

DerivationProof sketch: reducing the halting problem
  1. M ⟼ ΦMis computableM\ \longmapsto\ \Phi_M\quad\text{is computable}

    Given a Turing machine MM, build a finite set ΦM\Phi_M of sentences describing its run on the empty tape: a constant 00 and a successor function ss for time steps and tape cells; predicates Qq(t)Q_q(t) (state qq at time tt), H(t,p)H(t,p) (head at cell pp) and Sa(t,p)S_a(t,p) (symbol aa in cell pp); axioms for the initial configuration; and one axiom per transition, plus frame axioms, saying how configuration tt determines configuration s(t)s(t).

  2. M halts  ⟺  ΦM⊨∃t Qhalt(t)M\ \text{halts}\iff\Phi_M\models\exists t\,Q_{\mathrm{halt}}(t)

    If MM halts after nn steps, nn applications of the transition axioms derive the halting configuration, so ΦM⊨∃t Qhalt(t)\Phi_M\models\exists t\,Q_{\mathrm{halt}}(t). If MM never halts, the intended structure (domain N\mathbb N, the true run) satisfies ΦM\Phi_M but not ∃t Qhalt(t)\exists t\,Q_{\mathrm{halt}}(t):

  3. HALT ≤m VALID\mathrm{HALT}\ \le_m\ \mathrm{VALID}

    So M↦(⋀ΦM⇒∃t Qhalt(t))M\mapsto\big(\bigwedge\Phi_M\Rightarrow\exists t\,Q_{\mathrm{halt}}(t)\big) 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 theoryDecidable?Complexity
Propositional logicyesSAT NP-complete; validity coNP-complete
Monadic first-order logic: unary predicates, no functions (Löwenheim, 1915)yessatisfiability NEXPTIME-complete
Bernays–Schönfinkel class: prefix ∃∗∀∗\exists^*\forall^*, no functionsyessatisfiability NEXPTIME-complete
Two-variable fragment FO2\mathrm{FO}^2 (Mortimer, 1975)yes, with the finite-model propertyNEXPTIME-complete (Grädel, Kolaitis & Vardi, 1997)
Guarded fragment (Andréka, van Benthem & Németi, 1998)yes2EXPTIME-complete (Grädel, 1999)
Presburger arithmetic (N,+)(\mathbb N,+) (Presburger, 1929)yesevery decision procedure needs 22cn2^{2^{cn}} time in the worst case (Fischer & Rabin, 1974)
Real closed fields (R,+,×,<)(\mathbb R,+,\times,<) (Tarski, 1951)yes, by quantifier eliminationdoubly exponential in general
Full first-order logic; arithmetic (N,+,×)(\mathbb N,+,\times)novalidity is r.e.; arithmetic truth is not even arithmetically definable (Tarski)
Many description logics, the basis of ontology languages such as OWL, are fragments of the two-variable or guarded families; see the sibling lesson Description Logics & Ontologies.

The reasons for decidability vary: a bounded or finite model property (monadic, Bernays–Schönfinkel, FO2\mathrm{FO}^2), 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 ×\times 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.

Check your understanding

Which of these is decidable?

  1. The first-order theory of (N,+,×)(\mathbb N,+,\times)
  2. Whether a polynomial equation with integer coefficients has an integer solution
  3. The first-order theory of (R,+,×,<)(\mathbb R,+,\times,<)
  4. Validity of first-order sentences over a single binary predicate
Show the answer

C. The first-order theory of (R,+,×,<)(\mathbb R,+,\times,<)

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

DerivationProof sketch
  1. ProvT(y) :≡ ∃x PrfT(x,y)\mathrm{Prov}_T(y)\ :\equiv\ \exists x\ \mathrm{Prf}_T(x,y)

    Arithmetization. Code formulas and proofs as numbers ⌜φ⌝\ulcorner\varphi\urcorner. The relation "xx codes a TT-proof of the formula coded by yy" is decidable, hence represented in Q\mathsf Q by a formula PrfT(x,y)\mathrm{Prf}_T(x,y):

  2. T⊢GT↔¬ProvT(⌜GT⌝)T\vdash G_T\leftrightarrow\neg\mathrm{Prov}_T(\ulcorner G_T\urcorner)

    Diagonal lemma. For every formula ψ(y)\psi(y) there is a sentence δ\delta with Q⊢δ↔ψ(⌜δ⌝)\mathsf Q\vdash\delta\leftrightarrow\psi(\ulcorner\delta\urcorner). Applied to ¬ProvT(y)\neg\mathrm{Prov}_T(y) it gives a sentence that says "I am not provable":

  3. T consistent ⟹ T⊬GTT\ \text{consistent}\ \Longrightarrow\ T\nvdash G_T

    If T⊢GTT\vdash G_T, some number nn codes the proof, and Q\mathsf Q verifies the true numerical fact PrfT(nˉ,⌜GT⌝)\mathrm{Prf}_T(\bar n,\ulcorner G_T\urcorner), so T⊢ProvT(⌜GT⌝)T\vdash\mathrm{Prov}_T(\ulcorner G_T\urcorner); with the diagonal sentence, T⊢¬GTT\vdash\neg G_T as well, contradicting consistency. So T⊬GTT\nvdash G_T, which makes GTG_T true in N\mathbb N, since that is exactly what it says:

  4. T⊢ConT→GTT\vdash\mathrm{Con}_T\rightarrow G_T

    If T⊢¬GTT\vdash\neg G_T, then T⊢ProvT(⌜GT⌝)T\vdash\mathrm{Prov}_T(\ulcorner G_T\urcorner) although no number codes a proof: an ω\omega-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, TT can formalize the previous step and prove ConT→GT\mathrm{Con}_T\rightarrow G_T, so T⊢ConTT\vdash\mathrm{Con}_T would give T⊢GTT\vdash G_T. ∎

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): Γ⊨φ\Gamma\models\varphi iff Γ⊢φ\Gamma\vdash\varphi. 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 Q\mathsf Q 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.

Question 1

Which hypotheses does the Gödel–Rosser first incompleteness theorem require of a theory TT?

  1. TT is complete and decidable
  2. TT is consistent, effectively axiomatized and interprets Robinson arithmetic
  3. TT is first-order and has an infinite model
  4. TT contains set theory
Show the answer

B. TT 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 Q\mathsf Q.

Question 2

First-order logic is complete (Gödel, 1929), yet Peano arithmetic is incomplete (Gödel, 1931). How can both hold?

  1. The 1931 theorem refuted the 1929 one
  2. Peano arithmetic is not a first-order theory
  3. Completeness applies only to finite models
  4. Completeness says that sentences true in every model of PA\mathsf{PA} are provable; GPAG_{\mathsf{PA}} is true in N\mathbb N but false in some nonstandard model, so it is not a consequence of PA\mathsf{PA}
Show the answer

D. Completeness says that sentences true in every model of PA\mathsf{PA} are provable; GPAG_{\mathsf{PA}} is true in N\mathbb N but false in some nonstandard model, so it is not a consequence of PA\mathsf{PA}

The theorems concern different notions: consequence over all models versus truth in the intended model. Since PA⊬GPA\mathsf{PA}\nvdash G_{\mathsf{PA}}, completeness guarantees a model of PA+¬GPA\mathsf{PA}+\neg G_{\mathsf{PA}}, necessarily nonstandard.

Question 3

Which set is recursively enumerable but not decidable?

  1. The satisfiable first-order sentences
  2. The valid propositional sentences
  3. The sentences true in (N,+,×)(\mathbb N,+,\times)
  4. 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.

Question 4

Presburger arithmetic (N,+)(\mathbb N,+) is decidable. What is known about its complexity?

  1. It is decidable in polynomial time
  2. Every decision procedure needs doubly exponential time in the worst case (Fischer & Rabin, 1974)
  3. It is decidable only for quantifier-free sentences
  4. 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 22cn2^{2^{cn}} lower bound for some constant c>0c>0, 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).