Decidable
From Free net encyclopedia
The word decidable has formal meaning in computability theory, the theory of formal languages, and mathematical logic.
- See decidable set for its meaning in computability theory (historically called recursion theory).
- See decision problem for the definition of decidable problem in computability theory, an equivalent of the same basic notion, given from another "terminological" perspective.
- See decidable language for the equivalent in formal languages.
- See decidability (logic) for the equivalent in mathematical logic.
- See Gödel's incompleteness theorem for a theorem on the indecidability of languages consisting of "true statements" in mathematical logic.