Computability 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, feasible 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.

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. Novikov and 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 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 in finitely many variables over the rationals has a solution over the rationals.

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

Relative computability

Recursion theory in mathematical logic has traditionally focused on relative computability, a generalization of Turing computability. Informally, a set of natural numbers A is computable relative to a set B if there is an algorithm for deciding membership in A that is allowed to make arbitrary queries about the membership of (other) natural numbers in B. This notion is made precise through the definition of a Turing reduction.

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.

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]. 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. The even stronger notion of degrees of constructibility is studied in set theory.

Relationships between definability and noncomputability

The are close relationships between the degree of uncomputability 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. Godel'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 undefinability and in terms of uncomputability.

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 original description of the "computable" real numbers was a more natural and widely understood piece of terminology than that 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. A second effect of Rogers' proposal is that it removes from recursion theory fields such as computational complexity and Kolmogorov complexity of natural numbers, because the concepts in these fields are not invariant under computable bijections.

On the other hand, others point to the fact that the notion of noncomputability, and the acceptance of the need at a practical level to compare degrees of computability, have a long history (the Oxford English Dictionary traces its first recorded use of the word "incomputable" to 1606). According to this view "computability" refers quite legitimately, in both a practical and theoretical context, to the assessment of the extent of what can be computed, and what can be computed relatively. There is a growing interdisciplinary research community grouped around this reinstatement of the Turing terminology, bringing together mathematicians, computer scientists, philosophers, physicists, and others from the natural sciences. See for instance the Computability in Europe network, and its series of annual conferences.

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.

See also

• Turing degree
• Many-one reduction
• Enumeration reduction
• Hyperarithmetic theory
• Arithmetical hierarchy
• Analytical hierarchy
• Effective descriptive set theory
• Turing machine

References

Undergraduate level texts

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

Advanced texts and research papers

• M. Davis, ed. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, New York, 1965.
• Herbert B. Enderton [1977] : Elements of Recursion Theory, in : Jon Barwise, ed., Handbook of Mathematical Logic, pp. 527-566.
• Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel. Handbook of Recursive Mathematics. North-Holland, 1998.
• 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 0-444-87295-7
• Stephen Kleene (1952), Introduction to Metamathematics, North-Holland Publishing company, New York, (11th printing; 6th printing added comments), ISBN-0-7204-2103-9.
• Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
• Gerald E. Sacks. Higher Recursion Theory. Springer-Verlag, 1990.
• R. I. Soare, Computability and recursion, Bull. Symbolic Logic 2 (1996) 284-- 321.
• Robert I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0-387-15299-7