uncomputable

Uncomputable is a term in computability theory describing objects that cannot be computed by any algorithm running on a standard model of computation, such as a Turing machine. Typically this refers to functions that cannot be computed for all inputs, or decision problems for which no algorithm can determine the correct yes-or-no answer in every case.

A problem is decidable if a Turing machine exists that halts and answers correctly for every input; if no such machine exists, the problem is undecidable and the corresponding function is uncomputable.

Canonical example: the Halting problem asks whether a given program halts on a given input; this problem is undecidable and uncomputable. Proof uses diagonalization and reduction from the halting problem to itself. Other notable uncomputable functions include the Busy Beaver function, which, for a given n, is the maximum number of steps a halting n-state Turing machine can take before halting; its growth outpaces every computable function. Kolmogorov complexity K(x), the length of the shortest program producing x, is not computable. There are also uncomputable real numbers, and uncomputable sets such as those arising from certain Diophantine equations (Matiyasevich's theorem).

Most real numbers are uncomputable: a computable real allows algorithmic generation of its digits to any precision; noncomputable reals form the overwhelming majority of reals. Some uncomputable problems are recursively enumerable (semi-decidable), meaning yes instances can be confirmed by an algorithm, while no instances cannot be universally confirmed.

These results shape the limits of automatic reasoning and computation. The Church-Turing thesis provides a durable model of what it means to compute, and many uncomputable problems are shown via reductions from the Halting problem. Understanding uncomputability helps illuminate what machines cannot universally decide or produce.