Recursion theory

From Wikipedia, the free encyclopedia

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

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

The basic questions addressed by recursion theory are "What does it mean for a function from the natural numbers to themselves to be computable?" and "Can noncomputable functions be classified into a hierarchy based on their level of noncomputability?". The answers to these questions have led to a rich theory that is still being actively researched.

Recursion theorists in mathematical logic often study the theory of relative computability, reducibility notions, and degree structures described in this article. This contrasts with the theory of subrecursive hierarchies, formal methods, and formal languages that is common in the study of computability theory in computer science. 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 Computable and uncomputable sets 2 Turing computability 3 Relative computability and Turing degrees 4 Generalizations of Turing computability 5 Relationships between definability and computability 6 Name of the subject 7 Contemporary research 8 Notes 9 References 9.1 Undergraduate level texts 9.2 Advanced texts and survey papers 9.3 Research papers and collections

[edit] Computable and uncomputable sets

Recursion theory originated with work of Kurt Gödel, Alonzo Church, Alan Turing, Stephen Kleene and Emil Post in the 1930s.^[1] The fundamental results they obtained established Turing computability as the correct formalization of the informal idea of effective calculation. These results led to the Church-Turing thesis, which states that any function that is computable by an algorithm is computable by a Turing machine. Soare (1996) gives a complete history of this thesis.

With a rigorous definition of effective calculation came the first proofs that there are problems in mathematics that cannot be effectively decided. Church (1936a, 1936b) and Turing (1936) independently showed that the Entscheidungsproblem is not effectively decidable and Post (1947) 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.

Many problems of mathematics have been shown to be undecidable after these inital examples of the were established. Pyotr Sergeyevich Novikov and William Boone showed independently in the 1950s that the word problem for groups is not effectively solvable: 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. In 1970, Yuri Matiyasevich proved Matiyasevich's theorem, which implies that Hilbert's tenth problem has no effective solution; this problem asked whether there is an effective procedure to decide whether a Diophantine equation has a solution in the rational numbers. The list of undecidable problems gives additional examples of problems with no computable solution.

The study of which mathematical constructions can be effectively performed is sometimes called recursive mathematics; the Handbook of Recursive Mathematics (Ershov et al. 1998) covers many of the known results in this field.

[edit] Turing computability

The main form of computability studied in recursion theory was introduced by Turing (1936). A set of natural numbers is said to be computable or Turing computable if there is a Turing machine which, given a number n, halts with output 1 if n is in the set and halts with output 0 if n is not in the set. A function f from the natural numbers to themselves is a (Turing) computable function if there is a Turing machine which, on input n, halts and returns output f(n). The use of Turing machines here is not necessary; there are many other models of computation that have the same computing power as Turing machines.

Not every set of natural numbers is computable. The Halting problem, which is the set of (descriptions of) Turing machines that halt on input 0, is a well known example of a noncomputable set. The existence of many noncomputable sets follows from the facts that there are only countably many Turing machines, and thus only countably many computable sets, but there are uncountably many sets of natural numbers.

[edit] Relative computability and Turing degrees

Recursion theory in mathematical logic has traditionally focused on relative computability, a generalization of Turing computability defined using oracle Turing machines, introduced by Turing (1939). An oracle Turing machine is a hypothetical device which, in addition to performing the actions of a regular Turing machine, is able to ask questions of an oracle, which is a particular set of natural numbers. The oracle machine may ask questions of the form "Is n in the oracle set?". Each question will be immediately answered correctly, even if the oracle set is not computable. Thus an oracle machine with a noncomputable oracle will be able to compute sets that are not computable without an oracle.

Informally, a set of natural numbers A is Turing reducible to a set B if there is an oracle machine that correctly tells whether numbers are in A when run with B as the oracle set. In this case, the set A is said to be relatively computable from B.

If a set A is Turing reducible to a set B and B is Turing reducible to A then the sets are said to have the same Turing degree (also called degree of unsolvability). The Turing degree of a set gives a precise measure of how uncomputable the set is. The study of Turing degrees was initiated by Kleene and Post (1954), and since then a large amount of research in recursion theory has been devoted to the properties of the Turing degrees. Early research, such as that by Kleene and Post, focused on the properties of particular Turing degrees. More recent research has focused on the overall structure of the set of Turing degrees. A recent survey by Ambos-Spies and Fejer (2006) gives an overview of this research and its historical progression.

[edit] Generalizations of Turing computability

Recursion theory includes the study of generalized notions of computability such as hyperarithmetical reducibility and α-recursion theory, as described by Sacks (1990). These generalized computability notions are more set-theoretic in nature than Turing computability, which requires little more than the theory of the natural numbers to formalize. Both Turing computability and hyperarithmetical reducibility are important in the field of effective descriptive set theory. The even stronger notion of degrees of constructibility is studied in set theory.

[edit] Relationships between definability and computability

There are close relationships between the Turing degree of a set of natural numbers and the difficulty (in terms of the arithmetical hierarchy) of defining that set using a first-order formula. One such relationship is made precise by Post's theorem. A weaker relationship was demonstrated by Kurt Gödel in the proof of his incompleteness theorems. Gödel's proofs show that the set of logical consequences of an effective first-order theory form a recursively enumerable set, and that if the theory is strong enough this set will be uncomputable. Similarly, Tarski's indefinability theorem can be interpreted both in terms of definability and in terms of computability.

Recursion theory is also linked to second order arithmetic, a formal theory of natural numbers and sets of natural numbers. The fact that certain sets are computable or relatively computable often implies that these sets can be defined in weak subsystems of second order arithmetic. The program of reverse mathematics uses these subsystems to measure the noncomputability inherent in well known mathematical theorems. Simpson (1999) discusses many aspects of second-order arithmetic and reverse mathematics.

The field of proof theory includes the study of second-order arithmetic, Peano arithmetic, and formal theories of the natural numbers weaker than Peano arithmetic. One method of classifying the strength of these weak systems is by characterizing which computable functions the system can prove to be total (see Fairtlough and Wainer (1998)). For example, in primitive recursive arithmetic any computable function that is provably total is actually primitive recursive, while Peano arithmetic proves that functions like the Ackerman function, which are not primitive recursive, are total. Not every total computable function is provably total in Peano arithmetic, however; an example of such a function is provided by Goodstein's theorem.

[edit] Name of the subject

The field of mathematical logic dealing with computability and its generalizations has been called "recursion theory" since its early days. Robert I. Soare, a prominent researcher in the field, has proposed (Soare 1996) that the field should be called "computability theory" instead. He argues that Turing's terminology using the word "computable" is more natural and more widely understood than the terminology using the word "recursive" introduced by Kleene. Many contemporary researchers, perhaps swayed by Soare's argument, have changed to this alternate terminology. 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 ^[2] and Simpson^[3]. Some commentators argue that both the names Recursion theory and Computability theory fail to convey the fact that most of the objects studied in recursion theory are not computable. ^[4]

Rogers (1967) has suggested that a key property of recursion theory is that its results and structures should be invariant under computable bijections on the natural numbers (this suggestion draws on the ideas of the Erlangen program in geometry). The idea is that a computable bijection merely renames numbers in a set, rather than indicating any structure in the set, much as a rotation of the Euclidean plane does not change any geometric aspect of lines drawn on it. Since any two infinite computable sets are linked by a computable bijection, this proposal identifies all the infinite computable sets (the finite computable sets are viewed as trivial). Thus, to the extent that Rogers' proposal is correct, the only objects left for study are noncomputable sets, partitioned into equivalence classes by computable bijections of the natural numbers.

[edit] Contemporary research

There are many unsolved questions in recursion theory. 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 recursion theory research is the study of algorithmic randomness and related reducibility notions. A research conference in this area will be held in January 2007.^[5]

The main professional organization for recursion theory is the Association for Symbolic Logic,^[6] which holds several research conferences each year. The interdisciplinary research group Computability in Europe ^[7] plans a series of annual conferences through at least 2010.

[edit] Notes

1. ^ Many of these foundational papers are collected in The Undecidable edited by Martin Davis.
2. ^ http://weblog.fortnow.com/2004/02/is-it-recursive-computable-or.html
3. ^ http://www.cs.nyu.edu/pipermail/fom/1998-August/001993.html
4. ^ http://www.cs.nyu.edu/pipermail/fom/1998-August/002017.html
5. ^ http://www-2.dc.uba.ar/logic2007/
6. ^ http://www.aslonline.org/index.htm
7. ^ http://www.maths.leeds.ac.uk/cie/

[edit] References

[edit] Undergraduate level texts

• S. B. Cooper, 2004. Computability Theory, Chapman & Hall/CRC, ISBN 1-58488-237-9.
• N. Cutland, 1980. Computability, An introduction to recursive function theory, Cambridge University Press, ISBN 0-521-29465-7.
• Yuri Matiyasevich, 1993. Hilbert's Tenth Problem, MIT Press. ISBN 0-262-13295-8. An account at the undergraduate level by the mathematican who completed the solution of the problem.

[edit] Advanced texts and survey papers

• K. Ambos-Spies and P. Fejer, 2006. "Degrees of Unsolvability" (unpublished preprint). http://www.cs.umb.edu/~fejer/articles/History_of_Degrees.pdf
• H. Enderton, 1977. "Elements of Recursion Theory" Handbook of Mathematical Logic, edited by J. Barwise (North-Holland 1977), pp. 527-566. ISBN 0-7204-2285-X
• Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, 1998. Handbook of Recursive Mathematics. North-Holland, 1998. ISBN 0-7204-2285-X.
• M. Fairtlough and S. Wainer, 1998. "Hierarchies of Provably Recursive Functions". In Handbook of Proof Theory, edited by S. Buss, Elsevier, 1998.
• S. Kleene, 1952. Introduction to Metamathematics, North-Holland (11th printing; 6th printing added comments), ISBN-0-7204-2103-9.
• P. Odifreddi, 1989. Classical Recursion Theory, North-Holland, ISBN 0-444-87295-7.
• H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability. Second edition 1987, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1.
• G Sacks, 1990. Higher Recursion Theory, Springer-Verlag. ISBN 3-540-19305-7
• S. G. Simpson, 1999. Subsystems of Second Order Arithmetic, Springer-Verlag. ISBN 3-540-64882-8.
• R. I. Soare, 1996. Computability and recursion, Bulletin of Symbolic Logic v. 2 pp. 284–321.
• R. I. Soare, 1987. Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0-387-15299-7.

[edit] Research papers and collections

• A. Church, 1936a. "An unsolvable problem of elementary number theory." American Journal of Mathematics v. 58, pp. 345–363. Reprinted in "The Undecidable", M. Davis ed., 1965.
• A. Church, 1936b. "A note on the Entscheindungsproblem." Journal of Symbolic Logic 1, n. 1, and v. 3, n. 3. Reprinted in "The Undecidable", M. Davis ed., 1965.
• M. Davis, ed., 1965. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, New York. Reprint, Dover, 2004. ISBN 0-486-43228-9.
• S. C. Kleene and E. L. Post, 1954. "The upper semi-lattice of degrees of recursive unsolvability". Annals of Mathematics v. 2 n. 59, 379--407.
• E. Post, 1947. "Recursive unsolvability of a problem of Thue." Journal of Symbolic Logic v. 12 pp. 1–11. Reprinted in "The Undecidable", M. Davis ed., 1965.
• A. Turing, 1937. "On computable numbers, with an application to the Entscheindungsproblem." Proceedings of the London Mathematics Society, ser. 2 v. 42, pp. 230–265. Corrections ibid. v. 43 (1937) 544–546. Reprinted in "The Undecidable", M. Davis ed., 1965.
• A. Turing, 1939. "Systems of logic based on ordinals." Proceedings of the London Mathematics Society, ser. 2 v. 45, pp. 161–228. Reprinted in "The Undecidable", M. Davis ed., 1965.