Recursion theory

Encyclopedia : R : RE : REC : Recursion theory

For the branch of computer science called computability theory, see Computability theory (computer science).

Recursion theory, or computability theory, is a branch of mathematical logic. It originated in the study of computable functions and Turing degrees. The field grew to include the study of generalized computability and definability. In these areas, the theory overlaps with proof theory and effective descriptive set theory.

Computability theorists in mathematical logic often study the theory of relative computability, reducibility notions, and degree structures. This contrasts with the theory of subrecursive hierarchies, feasibile computation, and formal languages that is common in the study of computability theory by computer scientists. There is considerable overlap in knowledge and methods between these two research communities, however, and no firm line can be drawn between them.

Contents

1 History and Scope
2 Name of the subject
3 Contemporary research
4 Links
5 Notes
6 References

History and Scope

Computability theory originated with work of Kurt Gödel, Alonzo Church, Alan Turing, Stephen Kleene and Emil Post in the 1930's. The fundamental results they obtained established Turing computability as the correct formalization of the informal idea of effective calculation. With a rigorous definition of effective calculation came the first proofs that there are problems in mathematics that cannot be effectively decided. Church and Turing indepdendently showed that the Entscheidungsproblem was not effectively decidable and Post showed that the problem of determining whether a string in a Thue system has a normal form (similar to the question of whether a term in the λ calculus has a normal form) cannot be effectively decided.

The study of degree structures, including the Turing degrees, many-one degrees, and similar structures, is an important part of the field. The study of Turing degrees was initiated by Kleene and Post [1954]. A great deal of the research in computability theory has been devoted to the properties of the Turing degrees and the r.e Turing degrees. Beginning in the 1970s, the focus of the study of Turing degrees began to shift from local structural properties to global properties such as automorphisms and definability of relations.

Many problems of mathematics have been shown to be undecidable after the inital examples of the 1930s were established. Novikov and Boone showed in the 1950s that there is no effective procedure that, given a word in a finitely presented group, will decide whether the element represented by the word is the identity element of the group. This result has been used to show that many other problems are not decidable, such as the problem of whether two finite simplicial complexes represent homeomorphic spaces. In the 1970s, Yuri Matiyasevich gave a negative answer to Hilbert's tenth problem, which asked whether there is an effective procedure to decide whether a Diophantine equation in finitely many variables over the rationals has a solution over the rationals. This negative solution was a strengthening of a partial solution given by Martin Davis, Hilary Putnam, and Julia Robinson in 1961.

Recursion theory includes the study of generalized notions of computability such as hyperarithmetical reducibility, α-recursion theory, and degrees of constructibility. Strong analogies have been found between these generalized computability notions, which are of a set-theoretic character, and the classical notion of Turing computability, which is of an arithmetical character. Both Turing computability and hyperarithmetical reducibility are important in the field of effective descriptive set theory.

Name of the subject

The field of mathemetical logic dealing with computability and its generalizations has been called recursion theory since its early days. Robert Soare, a prominent researcher in the field, made a strong argument [Soare 1996] that the field should be called computability theory instead. Many contemporary researchers, prehaps swayed by Soare's argument, have begun to use this name. These researchers also use terminology such as partial computable function and computably enumerable (c.e.) set instead of partial recursive function and recursively enumerable (r.e.) set. Not all researchers have been convinced, however, as explained by Fortnow http://weblog.fortnow.com/2004/02/is-it-recursive-computable-or.html and Simpsonhttp://www.cs.nyu.edu/pipermail/fom/1998-August/001993.html.

Contemporary research

There are many unsolved questions about the Turing degrees and computably enumerable sets. The question of whether there is a nontrival automorphism of the Turing degrees is one of the main unsolved questions in this area.

A recent trend in computability theory is the study of algorithmic randomness and related reducibility notions.

Notes

References

S. Barry Cooper, Computability Theory, Chapman & Hall/CRC, ISBN 1584882379 (textbook)
Nigel J. Cutland, Computability, An introduction to recursive function theory, Cambridge University Press, ISBN 0521294657 (paperback), 1980.
Herbert B. Enderton [1977] : Elements of Recursion Theory, in : Jon Barwise, ed., Handbook of Mathematical Logic, pp. 527-566.
S. C. Kleene and E. L. Post [1954], The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59, 379--407.
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)
R. I. Soare, Computability and recursion, Bull. Symbolic Logic 2 (1996) 284-- 321.
Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0387152997 (textbook)