Editing Decidability (logic) (section)

{{Short description|Whether a decision problem has an effective method to derive the answer}}
In [[logic]], a true/false [[decision problem]] is '''decidable''' if there exists an [[effective method]] for deriving the correct answer. [[Zeroth-order logic]] (propositional logic) is decidable, whereas [[first-order logic|first-order]] and [[higher-order logic|higher-order]] logic are not. [[Formal system|Logical system]]s are decidable if membership in their set of [[Validity (logic)|logically valid]] formulas (or theorems) can be effectively determined. A [[Theory (mathematical logic)|theory]] (set of sentences [[Deductive closure|closed]] under [[logical consequence]]) in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory. Many important problems are [[undecidable problem|undecidable]], that is, it has been proven that no effective method for determining membership (returning a correct answer after finite, though possibly very long, time in all cases) can exist for them.