Decider

A decider, in computability theory, is a type of Turing machine that halts on every input and correctly decides membership in a language. Given a language L over an alphabet, a decider M accepts x if x is in L and rejects x if x is not in L; the crucial point is that M halts on all inputs.

A language is decidable if there exists a decider for it. Deciders are contrasted with recognizers (or semi-decision procedures), which may halt and accept for strings in the language but are not required to halt for strings not in the language. If a decider exists, the language is decidable; if no decider exists, the language is undecidable. The Halting problem is a classic example of an undecidable problem: there is no decider that determines, for every program and input, whether the program halts.

Examples of decidable languages include the set of even-length binary strings or the set of palindromes, both of which can be decided by a TM that halts on all inputs. Many questions in formal language theory are decidable, while a substantial number of questions in mathematics and logic are undecidable.

Beyond computability, the term decider can appear in decision theory and systems design to refer more loosely to a decision-maker or a component that implements a rule-based choice among alternatives. In software and AI, a decider component selects actions or outputs according to a specified policy or model.