A decision problem asks a yes or no question about its input, such as whether a given number is prime or whether a logical formula is provable. A problem is decidable when there exists an algorithm that, for every possible input, halts after finitely many steps and returns the correct yes or no answer. The Stanford Encyclopedia of Philosophy treats decidable as a synonym for solvable and recursive in this context.
A problem is undecidable when no such always-halting algorithm exists. This is not a statement about current technology or cleverness; it is a proven mathematical limit. The most famous example is the halting problem, which asks whether an arbitrary program will eventually stop on a given input. Turing showed that “some Turing machines on certain inputs never halt” and that no general procedure can decide the question for all cases.
Decidability is tied to the Church-Turing thesis. Because Turing machines, the lambda calculus, and recursive functions define the same class of computable procedures, a problem that no Turing machine can decide cannot be decided by any equivalent formal method either.
The first major undecidability result was Church and Turing’s independent demonstration in 1936 that the decision problem for first-order logic has no algorithmic solution. Decidability has been a guiding concept of theoretical computer science ever since, separating questions a machine can settle from those it provably cannot.