Computability is the branch of mathematical logic that asks which problems can be solved by a computing device in principle, setting aside questions of speed or memory. The Stanford Encyclopedia of Philosophy frames it directly: “A mathematical problem is computable if it can be solved in principle by a computing device.” The terms solvable, decidable, and recursive are used as near synonyms in this setting.
The boundary of computability was fixed in the 1930s by several independent models that turned out to be equivalent in power. Alan Turing’s abstract machines, Alonzo Church’s lambda calculus, and the theory of recursive functions all single out exactly the same class of computable functions. This convergence is the main evidence for the Church-Turing thesis, which holds that these formal models capture the informal idea of effective computation.
Crucially, computability theory also marks out what lies beyond the boundary. Turing showed that a universal machine can run any program, yet “some Turing machines on certain inputs never halt,” and there is no general procedure to tell in advance which will. Problems of this kind are called uncomputable or undecidable.
The field gives computer science its bedrock results: a precise definition of algorithm, a proof that some well-posed problems have no algorithmic solution, and the framework that later distinguishes what is merely computable from what is computable within practical limits.