Computability theory

Summary

Computability theory, also called recursion theory, studies which functions and sets of natural numbers can be computed by an algorithm. Its basic objects are computable functions, defined through Turing machines or through general recursive functions. It proves that some problems, such as the halting problem, have no algorithmic solution. It then compares unsolvable problems by reductions, which leads to Turing degrees and to hierarchies of definable sets.