Computable

Computable is a term used in mathematics and computer science to describe problems, functions, or processes that can be carried out by a finite, well-defined sequence of steps, i.e., an algorithm. For a total function f from natural numbers to natural numbers, computability means there exists an algorithm that, for every input n, halts and outputs f(n). In the context of decision problems, a language is computable (decidable) if there is an algorithm that, given any input string, halts and accepts when the string is in the language and rejects otherwise. If an algorithm may not halt on some inputs, the problem is not computable, though it may still be semi-decidable (recursively enumerable).

Computability is studied through formal models such as Turing machines, the lambda calculus, and the class of mu-recursive functions; these models are equally powerful in the sense that they compute the same class of total computable functions. The Church-Turing thesis informally states that any function that can be computed by an effective procedure can be computed by a Turing machine, and by extension by these other models.

There are well-defined problems that are not computable. The halting problem—determining whether a given program halts on a given input—is a canonical example of a noncomputable problem. Some noncomputable problems are semi-decidable, meaning there exists an algorithm that halts and accepts on inputs in the language but may run forever on others.

Computability theory clarifies the limits of algorithmic computation and underpins areas such as complexity theory, algorithm design, and formal verification. It traces its origins to work in the 1930s by Alan Turing, Alonzo Church, and others and continues to influence theoretical and practical computer science.