de Beauvoir, Simone See EXISTENTIALISM. decidability, as a property of sets, the existence of an effective procedure (a ‘decision procedure’) which, when applied to any object, determines whether or not the object belongs to the set. A theory or logic is decidable if and only if the set of its theorems is. Decidability is proved by describing a decision procedure and showing that it works. The truth table method, for example, establishes that classical propositional logic is decidable. To prove that something is not decidable requires a more precise characterization of the notion of effective procedure. Using one such characterization (for which there is ample evidence), Church proved that classical predicate logic is not decidable. See also CHURCH’S THE- SIS , TRUTH TABLE , TURING MACHIN. S.T.K.