decidability

Decidability is a property of a decision problem. A problem is decidable if there exists an algorithm that, for every possible input instance, terminates with the correct answer yes or no. If no such algorithm exists, the problem is undecidable. In the standard theory of computation, decidability is studied using abstract machines, most commonly Turing machines; a problem is decidable if a deterministic Turing machine halts on every input and outputs the correct result.

Decidable problems include many basic questions about formal languages and computation. For example, given a string and a finite automaton (DFA), the question of whether the string is accepted is decidable. Equivalently, many questions about regular languages, such as language membership, emptiness, and equivalence of DFAs, are decidable. Deterministic polynomial-time primality testing is another well-known decidable problem. On the other hand, several fundamental questions are undecidable. The halting problem—whether a given program finishes running on a given input—has no general algorithm that halts on all inputs with the correct yes/no answer. Other undecidable problems include the Post correspondence problem and Hilbert’s 10th problem (solvability of Diophantine equations). The Entscheidungsproblem, asking whether first-order logic sentences are universally valid, is also undecidable.

Some problems are semi-decidable (recursively enumerable): there exists an algorithm that will halt and accept on yes-instances but may run forever on no-instances. The halting problem is a classic example. Decidability is robust across reasonable computational models, in line with the Church–Turing thesis, which equates effective algorithms with Turing-machine computability. Rice’s theorem further shows that every nontrivial semantic property of programs is undecidable.