What does decidable mean?
"Decidable" is an adjective meaning capable of being decided, determined, or conclusively answered. Its most prominent modern home is mathematical logic and theoretical computer science, where a problem is called decidable if there exists an effective procedure — an algorithm — that correctly returns a yes-or-no answer for every instance. This technical sense carries great weight: Alan Turing's proof that the halting problem is not decidable showed that some legitimate questions can never be settled by any mechanical method, making the term central to the foundations of computation. Outside mathematics, the word sees more limited formal use, typically in legal or administrative contexts to describe disputes or issues that can be definitively resolved, as opposed to those left open or unresolvable. It derives from the Latin decidere, "to cut off" or "to determine," via English "decide." Its natural opposite, "undecidable," shares its technical prominence, and the pair encapsulates a profound idea: that the very answerability of a question can be a deep and sometimes negative result.
adjectiveCapable of being decided, settled, or determined; in logic and mathematics, referring to a problem or question for which an effective procedure exists that yields a yes-or-no answer in every case.
- (Logic and mathematics) Of a problem, question, or set of statements: capable of being resolved as true or false by an effective procedure or algorithm.
- (General use) Capable of being decided, determined, or settled.
"The dispute was finally taken to arbitration because it was decidable by no other means."
"Whether a given program halts on all inputs is not, in general, a decidable question."
"The committee agreed that the boundary dispute was decidable through a simple survey rather than lengthy litigation."
In mathematics, some perfectly well-formed questions can never be answered by any algorithm at all — Turing proved it — which makes "decidable" one of the most consequential adjectives in computer science.
Reviewed by Deb Chak, Editor. AI-assisted content curated by RJS Tech Solutions LLP.
Etymology of decidable
"Decidable" derives from the verb "decide," which entered English from French décider, ultimately from Latin decidere, formed from de- ("down, away") and caedere ("to cut") — literally "to cut off," hence to settle or determine a matter. The adjective formation with the suffix -able dates to roughly the early modern period, with the specialized logical sense emerging in the twentieth century alongside work on computability by Gödel, Church, and Turing. It thus shares its Latin root with related words such as "decision," "decisive," and "concise."
Related word forms
How decidable is actually used
"Decidable" is chiefly a technical term in mathematical logic and theoretical computer science, where it contrasts with "undecidable" in the precise sense established by Gödel and Turing. In ordinary prose it appears mostly in formal or legal contexts describing matters that can be definitively settled.
Easily confused with decidable
"Decided" means definite or unmistakable (a decided advantage), while "decidable" means capable of being decided.
"Decisive" describes something or someone that settles an issue conclusively, whereas "decidable" merely indicates that a decision or determination is possible.