computability

Computability theory studies which functions can be computed by effective procedures. A function is computable if there exists a finite algorithm that, given any valid input, produces the correct output in finite time. The field formalizes this idea with models such as Turing machines, partial recursive functions, and lambda calculus. The Church-Turing thesis claims that these models capture the intuitive notion of effective computability, and while not provable, it is widely accepted as a guiding principle.

Decidability concerns problems that admit a procedure which always halts with a yes or no answer. Some problems are decidable; others are not. A central result is the undecidability of the halting problem: no algorithm can determine, for every program and input, whether the program halts. Reductions show undecidability by transforming a known hard problem into the problem under study.

Related concepts include semi-decidability (recursively enumerable sets), where a Turing machine may halt on yes-instances but not on others. Rice's theorem states that every nontrivial semantic property of programs is undecidable. Complexity theory, in contrast, studies resource-bounded computation and asks not just what is computable, but what can be computed efficiently.

Impact: computability theory underpins the limits of algorithmic computation and informs logic, mathematics, and computer science. It complements complexity theory and influences formal verification, programming language theory, and the study of formal models of computation.