Decidability

A problem is decidable if some algorithm always halts with the correct yes-or-no answer for every input.

The definition

A decision problem is decidable (or recursive) if there exists a Turing machine that halts on every input and outputs the correct yes or no. Halting on every input is the strict part: a method that sometimes runs forever does not decide the problem, even if it is right whenever it stops.

Decidable versus recognizable

A weaker property is recognizable (recursively enumerable): a machine that halts and says yes on all yes-instances, but may run forever on no-instances. Every decidable problem is recognizable, but not conversely. The halting problem is the classic recognizable-but-undecidable example.

• Decidable: always halts, always correct
• Recognizable: halts on yes, may loop on no
• Co-recognizable: halts on no, may loop on yes

A key symmetry

A problem is decidable if and only if both it and its complement are recognizable. If you can eventually confirm every yes and eventually confirm every no, you can run both searches in parallel and one will always finish, giving a deciding algorithm.

Examples of decidable problems

• Is a number prime
• Does a finite graph have a cycle
• Is a regular expression matched by a given string
• Do two finite automata accept the same language

Why the boundary matters

Decidability marks the outer edge of what algorithms can ever do, independent of speed. Inside that edge, complexity theory asks how expensive the answer is. Outside it, no amount of computing power helps. Knowing a problem is undecidable saves the wasted effort of seeking an algorithm that cannot exist.