COMPUTABILITY THEORY
The metatheory of computation: what functions and sets are effectively computable, decidable, or enumerable, and how the undecidable problems are stratified by degree and hierarchy. It is the recursion-theoretic branch of mathematical logic, standing alongside model theory and proof theory.
Entries include the foundations (computability theory, recursive functions, the Church-Turing thesis), the core undecidability results (the halting problem, Rice's theorem), the structure of the non-computable (Turing degrees and the jump, recursively enumerable sets and the priority method), the classification hierarchies (the arithmetical hierarchy), the information-theoretic measure (Kolmogorov complexity), and the generalizations beyond the finite (higher recursion theory over admissible ordinals and higher types).