Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. Mathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation as part of the foundations of mathematics. ... It has been suggested that recursive function be merged into this article or section. ... In computability theory, the Turing degree of a subset of the natural numbers, , is the equivalence class of all subsets of equivalent to under Turing reducibility. ... Effective descriptive set theory is the branch of descriptive set theory dealing with sets of reals having lightface definitions; that is, definitions that do not require an arbitrary real parameter. ...

Classical computability theory originated with the seminal work of Kurt Gödel, Alonzo Church, Alan Turing, Stephen Kleene and Emil Post in the 1930's, and includes a wide spectrum of topics, such as the theory of reducibilities and their degree structures, computably enumerable sets and their automorphisms, subrecursive hierarchy classifications, computable structures, and computational complexity theory relating to the preceding. Kurt Gödel (IPA: ) (April 28, 1906 Brno, then Austria-Hungary, now Czech Republic – January 14, 1978 Princeton, New Jersey) was a logician, mathematician, and philosopher of mathematics. ... Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician who was responsible for some of the foundations of theoretical computer science. ... Alan Turing is often considered the father of modern computer science. ... Stephen Cole Kleene (January 5, 1909 - January 25, 1994) was an American mathematician whose work at the University of Wisconsin-Madison helped lay the foundations for theoretical computer science. ... Emil Leon Post (February 11, 1897 - April 21, 1954) was a Polish-American mathematician and logician. ... In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if There is an algorithm that, when given an input â€” typically an integer or a tuple of integers or a sequence of characters â€” eventually halts if and... In computer science, computational complexity theory is the branch of the theory of computation that studies the resources, or cost, of the computation required to solve a given problem. ...

Basic to recent developments in the subject is the theory of relative computability. This classifies real numbers according to the Turing reducibility relation a < b meaning 'a is computable from knowledge of b' (giving rise to the Turing universe of real numbers), and is captured mathematically via the Turing degree structure. (The structure of the enumeration degrees is the analogous structure derived from nondeterministic Turing reducibility.) Thus if a < b then a is closer to being 'outright computable' than b. Let 0 be the degree of all 'outright computable' reals. Then there is a natural jump operation a' on the degrees - also called the Turing jump - which gives rise to a linear scale 0 , 0' , 0' ' , .... against which other degrees may be measured. The ordering of the Turing degrees (and also of the enumeration degrees) is a very complex structure, requiring highly sophisticated and technically difficult methods for its analysis. Following the early work of Kleene and Post, its study has formed one of the central areas of research in computability theory over the last fifty years, yet it is only recently that some of the deeper patterns and interrelationships have emerged. Most recently, interest has focused on Turing definability (what can be naturally described in the structure of the Turing degrees), and automorphisms (giving a measure of the rigidity of the Turing universe). These topics promise to have far reaching mathematical, scientific and philosophical consequences. In computability theory relative computability or relativized computability is the study of computability concepts relative to a given set. ... In computability theory, a Turing reduction from a problem A to a problem B is, intuitively, a reduction which easily solves A, assuming B is easy to solve. ... In computability theory, the Turing degree of a subset of the natural numbers , is the equivalence class consisting of all subsets of equivalent to under Turing reducibility. ...

There are still very many open questions, both of a technical nature, concerning extensions of what is known about the Turing degrees and their context in the enumeration degrees, and similar questions for other natural reducibility degree structures, and less well-defined questions concerning the scope of relevance of such work.

A particularly exciting recent development is the renewal of the roots of classical computability in Turing's interest in everyday questions concerning the extent and nature of practical computability. This renewal has many facets, and involves new links between computability theorists, computer scientists, philosophers and theoretical physicists.

References

• S. Barry Cooper, Computability Theory, Chapman & Hall/CRC, ISBN 1584882379 (textbook)
• Piergiorgio Odifreddi, Classical Recursion Theory, North-Holland, ISBN 0444872957 (textbook)
• Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0262680521 (paperback), ISBN 0070535221 (textbook)
• Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0387152997 (textbook)