décidable

Décidable, in the context of mathematical logic and computer science, refers to a decision problem for which an algorithm exists that always halts and correctly answers yes or no for every input instance. More formally, a language L over a finite alphabet is decidable if there is a Turing machine that, given any word w, halts and accepts if w∈L and halts and rejects otherwise. Equivalently, L is decidable iff it is a recursive language.

Decidability contrasts with semi-decidability: a language is recursively enumerable if there is a machine that halts and accepts words in L but may loop on words not in L. Every decidable language is r.e., but not every r.e. language is decidable. The halting problem is a canonical example of an undecidable problem.

Many standard language classes are decidable: regular languages, deterministic context-free languages, and, in general, most problems about finite objects. By contrast, many natural problems about arithmetic and computation are undecidable: the general halting problem, and, for example, the validity of first-order statements over the natural numbers with multiplication (the theory of arithmetic) is undecidable; even the universal theory of Turing machine configurations is undecidable.

The term décidable is common in French-language texts, while English literature usually uses decidable or decidability; the concepts align via recursion theory and Turing computability.

Note: The decidability status of a problem can be independent of its resource requirements (time or space); a problem can be decidable but require very large time or space to solve.