Decidable

In computability theory, a decision problem is decidable if there exists an algorithm that, on every input, terminates with a correct yes or no answer. Equivalently, a language L over an alphabet Σ is decidable if there exists a Turing machine M that halts on every input w ∈ Σ* and accepts w when w ∈ L and rejects w when w ∉ L.

Decidable languages are precisely the recursive (computable) languages. They form a strict subset of the recursively enumerable (r.e.) languages; every decidable language is r.e., but there exist r.e. languages that are not decidable, as exemplified by the Halting problem.

Common examples illustrate the concept. Regular languages are decidable, with straightforward algorithms such as finite automata for membership testing. Deterministic context-free languages are also decidable, with parsing and membership algorithms like CYK. Classic undecidable problems include the Halting problem and the Entscheidungsproblem, which have no algorithm that decides them for all inputs.

Decidability is accompanied by closure properties: the class of decidable languages is closed under complement, union, and intersection, as well as under many other standard operations. This makes the set of decidable problems robust under combination and construction. In practice, many decision problems arising in mathematics, formal verification, and programming are decidable, though some fundamental questions remain undecidable or only semi-decidable (recognizable) under standard models of computation.