Editing Entscheidungsproblem (section)

== Generalizations ==
{{Main|Decidability (logic)#Decidability of a theory}}

Using the [[deduction theorem]], the Entscheidungsproblem encompasses the more general problem of deciding whether a given first-order sentence is entailed by a given finite set of sentences, but validity in first-order theories with infinitely many axioms cannot be directly reduced to the Entscheidungsproblem. Such more general decision problems are of practical interest. Some first-order theories are algorithmically [[decidability (logic)|decidable]]; examples of this include [[Presburger arithmetic]], [[real closed field]]s, and [[Type system#Static typing|static type systems]] of many [[programming language]]s. On the other hand, the first-order theory of the [[natural number]]s with addition and multiplication expressed by [[Peano axioms|Peano's axioms]] cannot be decided with an algorithm.