Mirror of English Wikipedia, the free encyclopedia

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.

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.

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.

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)