Uncomputability

Uncomputability refers to the property of certain problems or functions for which no algorithm can decide the answer for all possible inputs. In computability theory, a function is computable if a Turing machine exists that, given any valid input, halts with the correct output. A decision problem is decidable if there is an algorithm that always yields the correct yes/no answer; otherwise the problem is uncomputable.

The halting problem is the quintessential example. It asks whether a given computer program will halt on a given input. In 1936, Alan Turing proved that no general procedure can solve halting for all program-input pairs. This result demonstrates the existence of undecidable problems and illustrates fundamental limits to mechanical computation. The halting result underpins the Church-Turing thesis, which characterizes effective procedures as those computable by Turing machines.

Beyond halting, many other undecidable problems are known. The Entscheidungsproblem (Hilbert’s 10th problem) asks whether a given mathematical statement is universally valid; it is undecidable. The Post correspondence problem and the word problem for certain algebraic structures are also undecidable. Rice’s theorem shows that every nontrivial semantic property of the function computed by a program is undecidable, implying that broad questions about what programs do are typically unanswerable.

Computability theory distinguishes between decidable problems and those that are at best partially computable (recursively enumerable) or neither. A problem is recursively enumerable if there exists a Turing machine that halts and accepts on yes-instances but may run forever on no-instances. The halting problem is r.e.-complete, illustrating how some undecidable problems are still amenable to partial algorithmic treatment.

Uncomputability thus marks the boundary of algorithmic solvability, with wide implications for logic, mathematics, and computer science.