Noncomputable

Noncomputable is a term used in computability theory to describe objects that cannot be generated by any algorithm. Broadly, an object is noncomputable if no Turing machine (or equivalent formal model of computation) can produce it or decide it in general. This applies to functions, sets of natural numbers, and real numbers. In the real-number setting, a real is computable if there exists an algorithm that, given any desired precision, outputs a rational approximation of the real to that precision. Objects that resist such algorithmic generation are called noncomputable.

Common examples illustrate the concept. The halting problem, which asks whether a given program halts on a given input, is undecidable; the characteristic function of the halting set is a total but noncomputable function. Chaitin’s Omega is a particular noncomputable real number representing the halting probability of a universal machine. The Busy Beaver function, which grows faster than any computable function, is another canonical noncomputable object. There are also many noncomputable sets and properties that arise in mathematics and logic, including certain thresholds of Kolmogorov complexity.

A key size-theoretic and measure-theoretic fact is that most real numbers are noncomputable: the set of computable reals is countable, while the real numbers are uncountable. Similarly, computable functions form a countable class among all total functions. Noncomputability does not imply paradox or impossibility in practice; some noncomputable objects are definable and well-characterized, but no algorithm can compute them in all cases.

See also undecidable problem, computable function, decidability, Turing machine, Omega (incomputability).