In
logic, the term
decidable refers to the
decision problem, the question of the existence of an
effective method for determining membership in a set of formulas, or, more precisely, an algorithm that can and will return a Boolean true or false value (instead of looping indefinitely).
Logical systems such as
propositional logic are decidable if membership in their set of
logically valid formulas (or theorems) can be effectively determined. A
theory (set of sentences
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, that is, it has been proven that no effective method can exist for them.