Computability Theory
- is also known as recursion theory
- is a branch of mathematical logic and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory
Basic questions addressed by computability theory include:
- What does it mean for a function on natural numbers to be computable?
- How can non-computable functions be classified into a hierarchy based on their level of non-computability?