An undecidable problem is a decision problem - a question with a yes-or-no answer for each input - for which no algorithm can always produce the correct answer. The Stanford Encyclopedia of Philosophy frames decidability in terms of Turing machines: a set is decidable if and only if some total Turing machine decides, for every input, whether or not that input belongs to the set. A problem is undecidable precisely when no such machine exists, meaning no mechanical procedure can settle every case.
The classic example is the halting problem. The Stanford Encyclopedia explains that it is not computable to take a Turing machine together with its input and decide whether that machine will eventually halt. Turing established this through a self-referential, diagonal argument: assuming a halting decider exists leads to a contradiction, so no such decider can exist. The halting problem was the first natural problem shown to lie beyond the reach of any algorithm.
These results emerged in 1936. The Stanford Encyclopedia recounts that Alonzo Church and Alan Turing independently proved the unsolvability of the Entscheidungsproblem, Hilbert’s challenge to find a procedure that decides the validity of any first-order logical formula. Turing introduced his abstract machines, proved the halting problem unsolvable, and obtained the unsolvability of the Entscheidungsproblem as a corollary. Later examples, such as Hilbert’s tenth problem on integer solutions to polynomial equations, confirmed that undecidability is not a rare curiosity but a pervasive feature of computation, marking a hard limit on what algorithms can ever decide.