incomputable

Incomputable is a term used in computability theory to describe a function, problem, or quantity for which no algorithm can provide correct answers for all possible inputs. More formally, a function f: N → N is incomputable if there is no Turing machine that computes f(x) for every input x in a finite amount of time. A decision problem is incomputable if there is no algorithm that determines a correct yes-or-no answer for every instance.

Classic examples illustrate incomputability. The Halting problem asks whether a given computer program will halt on a given input; Alan Turing showed that no general algorithm can decide this for all programs, making the Halting problem incomputable. Related problems inherit this property through reductions. The Busy Beaver function, which describes the maximum number of steps a halting machine of a given size can take, grows faster than any computable function and is thus noncomputable. Some real numbers, such as Chaitin’s Omega, are incomputable in the sense that their infinite binary expansion cannot be generated by any algorithm.

Incomputability is distinct from but related to undecidability and computational complexity. A problem can be incomputable yet solvable for restricted inputs or by approximate, probabilistic, or heuristic methods. The concept highlights fundamental limits on what can be achieved with algorithms and formal systems.

Originating in the work of early 20th‑century logicians, including Turing and Church, incomputability remains a foundational notion in mathematics, computer science, and logic, shaping understandings of algorithmic limits, randomness, and formal provability. See also computability, decidability, halting problem, Turing machine, and Gödel’s incompleteness theorems.