Overview of Recursion Theory
Recursion-Theory, also known as Computability-Theory, is a fundamental branch of Mathematical-Logic and Theoretical-Computer-Science. It originated in the 1930s through the pioneering work of mathematicians such as Alan-Turing, Alonzo-Church, Kurt-Godel, and Stephen-Kleene. The field primarily investigates the nature of Computable-Functions and the limits of algorithmic calculation.
At the heart of the discipline is the Church-Turing-Thesis, which identifies the intuitive notion of effectively calculable functions with those computable by a Turing-Machine or defined via Lambda-Calculus. This framework allowed for the rigorous definition of Recursive-Sets and Recursively-Enumerable-Sets. One of the most significant results in this field is the proof of the Halting-Problem's undecidability, which established that there are well-defined mathematical problems for which no Algorithm exists.
Advanced topics within Recursion-Theory include the study of Turing-Degrees, which measure the level of algorithmic unsolvability of a set, and the Arithmetical-Hierarchy, which classifies sets based on the complexity of the formulas defining them. Theorems such as Rices-Theorem further demonstrate that all non-trivial semantic properties of programs are undecidable. External documentation and further reading are available via the Stanford Encyclopedia of Philosophy and the nLab.