→Recursion theory: added Rózsa Péter and source
'''[[Recursion theory]]''', also called '''computability theory''', studies the properties of [[computable function]]s and the [[Turing degree]]s, which divide the uncomputable functions into sets that have the same level of uncomputability. Recursion theory also includes the study of generalized computability and definability. Recursion theory grew from the work of [[Alonzo Church]] and [[Alan Turing]] in the 1930s, which was greatly extended by [[Stephen Cole Kleene|Kleene]] and [[Emil Leon Post|Post]] in the 1940s.
Classical recursion theory focuses on the computability of functions from the natural numbers to the natural numbers. The fundamental results establish a robust, canonical class of computable functions with numerous independent, equivalent characterizations using [[Turing machine]]s, [[lambda calculus|λ calculus]], and other systems. More advanced results concern the structure of the Turing degrees and the [[lattice (order)|lattice]] of [[recursively enumerable set]]s.