INCLUSION CRITERIA
An entry belongs in this subdivision if and only if its subject is the theory of computability: which functions or sets are computable, decidable, or enumerable, and the classification of problems by degree, jump, or hierarchy.
Required: At least one of the following:
- A model or thesis of effective computation (recursive functions, Turing machines, Church-Turing)
- A result about decidability or its failure (halting problem, Rice's theorem, r.e. sets)
- A structure of the non-computable (Turing degrees, arithmetical hierarchy, higher recursion, Kolmogorov complexity)
Not sufficient: A proof calculus (Proof-Systems). A model-theoretic result (Model-Theory). An applied decision procedure whose interest is engineering rather than computability theory (Applications).
Boundary: Descriptive and proof complexity are cross-listed with Model-Theory and Proof-Systems. Provability logic, though tied to incompleteness, is a modal system and lives in Modal/Alethic. The complexity of practical solving (SAT) lives in Proof-Systems; the theory of what is computable at all lives here.