|
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, the 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. 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. 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. 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 independently 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. Many problems of mathematics have been shown to be undecidable after the inital examples of the 1930s 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. 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 topological spaces. 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 a solution in the rational numbers. 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. Turing computability The main form of computability studied in recursion theory is Turing computability. 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. 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. 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. 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. 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. This relationship is made precise by Post's theorem. A weaker form of this 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. 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. 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 Soare, a prominent researcher in the field, made a strong argument Soare 1996 that the field should be called computability theory instead. He argued that Turing's terminology using the word "computable" was a more natural and more widely understood than the terminology introduced by Kleene, which was derived from the nineteenth century notion of "recursion". Many contemporary researchers, perhaps 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 and Simpson. 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 . 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. 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. The main professional organization for recursion theory is the Association for Symbolic Logic, which holds several research conferences each year. The interdisciplinary research group Computability in Europe plans a series of annual conferences through at least 2010. Notes Undergraduate level texts Advanced texts and research papers Elements of Recursion Theory, inJon Barwise, ed., Handbook of Mathematical Logic, pp. 527-566. | |||||||
|
| ||||||||
 |
|
| |