Computability theory, also known asrecursion theory, is a branch ofmathematical logic,computer science, and thetheory of computation that originated in the 1930s with the study ofcomputable functions andTuring degrees. The field has since expanded to include the study of generalizedcomputability anddefinability. In these areas, computability theory overlaps withproof theory andeffective descriptive set theory.
Basic questions addressed by computability theory include:
Although there is considerable overlap in terms of knowledge and methods, mathematical computability theorists study the theory of relative computability, reducibility notions, and degree structures; those in the computer science field focus on the theory ofsubrecursive hierarchies,formal methods, andformal languages. The study of which mathematical constructions can be effectively performed is sometimes calledrecursive mathematics.[a]
| n | 2 | 3 | 4 | 5 | 6 | ... | |
|---|---|---|---|---|---|---|---|
| Σ(n) | 4 | 6 | 13 | 4098 | ≥ 2↑↑↑5[2] | ? | |
| Does not appear TheBusy Beaver function Σ(n) grows faster than any computable function. Hence, it is not computable;[3] only a few values are known. | |||||||
Computability theory originated in the 1930s, with the work ofKurt Gödel,Alonzo Church,Rózsa Péter,Alan Turing,Stephen Kleene, andEmil Post.[4][b]
The fundamental results the researchers obtained establishedTuring computability as the correct formalization of the informal idea of effective calculation. In 1952, these results led Kleene to coin the two names "Church's thesis"[5]: 300 and "Turing's thesis".[5]: 376 Nowadays these are often considered as a single hypothesis, theChurch–Turing thesis, which states that any function that is computable by analgorithm is acomputable function. Although initially skeptical, by 1946 Gödel argued in favor of this thesis:[6]: 84
"Tarski has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an interesting epistemological notion, i.e., one not depending on the formalism chosen."[6]: 84 [7]
With a definition of effective calculation came the first proofs that there are problems in mathematics that cannot beeffectively decided. In 1936, Church[8][9] and Turing[10] were inspired by techniques used by Gödel to prove his incompleteness theorems - in 1931, Gödel independently demonstrated that theEntscheidungsproblem is not effectively decidable. This result showed that there is no algorithmic procedure that can correctly decide whether arbitrary mathematical propositions are true or false.
Many problems inmathematics have been shown to be undecidable after these initial examples were established.[c] In 1947,Markov and Post published independent papers showing that theword problem for semigroups cannot be effectively decided. Extending this result,Pyotr Novikov andWilliam Boone showed independently in the 1950s that theword problem for groups is not effectively solvable: there is no effective procedure that, given a word in a finitely presentedgroup, will decide whether the element represented by the word is theidentity element of the group. In 1970,Yuri Matiyasevich proved (using results ofJulia Robinson)Matiyasevich's theorem, which implies thatHilbert's tenth problem has no effective solution; this problem asked whether there is an effective procedure to decide whether aDiophantine equation over the integers has a solution in the integers.
The main form of computability studied in the field was introduced by Turing in 1936.[10] A set of natural numbers is said to be acomputable set (also called adecidable,recursive, orTuring computable set) if there is aTuring machine that, given a numbern, halts with output 1 ifn is in the set and halts with output 0 ifn is not in the set. A functionf from natural numbers to natural numbers is a(Turing)computable, orrecursive function if there is a Turing machine that, on inputn, halts and returns outputf(n). The use of Turing machines here is not necessary; there are many othermodels of computation that have the same computing power as Turing machines; for example theμ-recursive functions obtained from primitive recursion and the μ operator.
The terminology for computable functions and sets is not completely standardized. The definition in terms of μ-recursive functions as well as a different definition ofrekursiv functions by Gödel led to the traditional namerecursive for sets and functions computable by a Turing machine. The worddecidable stems from the German wordEntscheidungsproblem which was used in the original papers of Turing and others. In contemporary use, the term "computable function" has various definitions: according toNigel J. Cutland,[11] it is a partial recursive function (which can be undefined for some inputs), while according toRobert I. Soare[12] it is a total recursive (equivalently, general recursive) function. This article follows the second of these conventions. In 1996, Soare[13] gave additional comments about the terminology.
Not every set of natural numbers is computable. Thehalting 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 onlycountably many Turing machines, and thus only countably many computable sets, but according to theCantor's theorem, there areuncountably many sets of natural numbers.
Although the halting problem is not computable, it is possible to simulate program execution and produce an infinite list of the programs that do halt. Thus the halting problem is an example of acomputably enumerable (c.e.) set, which is a set that can be enumerated by a Turing machine (other terms for computably enumerable includerecursively enumerable andsemidecidable). Equivalently, a set is c.e. if and only if it is the range of some computable function. The c.e. sets, although not decidable in general, have been studied in detail in computability theory.
Beginning with the theory of computable sets and functions described above, the field of computability theory has grown to include the study of many closely related topics. These are not independent areas of research: each of these areas draws ideas and results from the others, and most computability theorists are familiar with the majority of them.
Computability theory in mathematical logic has traditionally focused onrelative computability, a generalization of Turing computability defined usingoracle Turing machines, introduced by Turing in 1939.[14] 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 to anoracle, which is a particular set of natural numbers. The oracle machine may only ask questions of the form "Isn 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 a Turing machine without an oracle cannot.
Informally, a set of natural numbersA isTuring reducible to a setB if there is an oracle machine that correctly tells whether numbers are inA when run withB as the oracle set (in this case, the setA is also said to be (relatively)computable fromB andrecursive inB). If a setA is Turing reducible to a setB andB is Turing reducible toA then the sets are said to have the sameTuring degree (also calleddegree of unsolvability). The Turing degree of a set gives a precise measure of how uncomputable the set is.
The natural examples of sets that are not computable, including many different sets that encode variants of thehalting problem, have two properties in common:
Many-one reductions are "stronger" than Turing reductions: if a setA is many-one reducible to a setB, thenA is Turing reducible toB, but the converse does not always hold. Although the natural examples of noncomputable sets are all many-one equivalent, it is possible to construct computably enumerable setsA andB such thatA is Turing reducible toB but not many-one reducible toB. It can be shown that every computably enumerable set is many-one reducible to the halting problem, and thus the halting problem is the most complicated computably enumerable set with respect to many-one reducibility and with respect to Turing reducibility. In 1944, Post[15] asked whetherevery computably enumerable set is either computable orTuring equivalent to the halting problem, that is, whether there is no computably enumerable set with a Turing degree intermediate between those two.
As intermediate results, Post defined natural types of computably enumerable sets like thesimple,hypersimple and hyperhypersimple sets. Post showed that these sets are strictly between the computable sets and the halting problem with respect to many-one reducibility. Post also showed that some of them are strictly intermediate under other reducibility notions stronger than Turing reducibility. But Post left open the main problem of the existence of computably enumerable sets of intermediate Turing degree; this problem became known asPost's problem. After ten years, Kleene and Post showed in 1954 that there are intermediate Turing degrees between those of the computable sets and the halting problem, but they failed to show that any of these degrees contains a computably enumerable set. Very soon after this, Friedberg and Muchnik independently solved Post's problem by establishing the existence of computably enumerable sets of intermediate degree. This groundbreaking result opened a wide study of the Turing degrees of the computably enumerable sets which turned out to possess a very complicated and non-trivial structure.
There are uncountably many sets that are not computably enumerable, and the investigation of the Turing degrees of all sets is as central in computability theory as the investigation of the computably enumerable Turing degrees. Many degrees with special properties were constructed:hyperimmune-free degrees where every function computable relative to that degree is majorized by a (unrelativized) computable function;high degrees relative to which one can compute a functionf which dominates every computable functiong in the sense that there is a constantc depending ong such thatg(x) < f(x) for allx > c;random degrees containingalgorithmically random sets;1-generic degrees of 1-generic sets; and the degrees below the halting problem oflimit-computable sets.
The study of arbitrary (not necessarily computably enumerable) Turing degrees involves the study of the Turing jump. Given a setA, theTuring jump ofA is a set of natural numbers encoding a solution to the halting problem for oracle Turing machines running with oracleA. The Turing jump of any set is always of higher Turing degree than the original set, and a theorem of Friedburg shows that any set that computes the Halting problem can be obtained as the Turing jump of another set.Post's theorem establishes a close relationship between the Turing jump operation and thearithmetical hierarchy, which is a classification of certain subsets of the natural numbers based on their definability in arithmetic.
Much recent research on Turing degrees has focused on the overall structure of the set of Turing degrees and the set of Turing degrees containing computably enumerable sets. A deep theorem of Shore and Slaman[16] states that the function mapping a degreex to the degree of its Turing jump is definable in the partial order of the Turing degrees. A survey by Ambos-Spies and Fejer[17] gives an overview of this research and its historical progression.
An ongoing area of research in computability theory studies reducibility relations other than Turing reducibility. Post[15] introduced severalstrong reducibilities, so named because they imply truth-table reducibility. A Turing machine implementing a strong reducibility will compute a total function regardless of which oracle it is presented with.Weak reducibilities are those where a reduction process may not terminate for all oracles; Turing reducibility is one example.
The strong reducibilities include:
Further reducibilities (positive, disjunctive, conjunctive, linear and their weak and bounded versions) are discussed in the articleReduction (computability theory).
The major research on strong reducibilities has been to compare their theories, both for the class of all computably enumerable sets as well as for the class of all subsets of the natural numbers. Furthermore, the relations between the reducibilities has been studied. For example, it is known that every Turing degree is either a truth-table degree or is the union of infinitely many truth-table degrees.
Reducibilities weaker than Turing reducibility (that is, reducibilities that are implied by Turing reducibility) have also been studied. The most well known arearithmetical reducibility andhyperarithmetical reducibility. These reducibilities are closely connected to definability over the standard model of arithmetic.
Rice showed that for every nontrivial classC (which contains some but not all c.e. sets) the index setE = {e: theeth c.e. setWe is inC} has the property that either thehalting problem or its complement is many-one reducible toE, that is, can be mapped using amany-one reduction toE (seeRice's theorem for more detail). But, many of these index sets are even more complicated than the halting problem. These type of sets can be classified using thearithmetical hierarchy. For example, the index set FIN of the class of all finite sets is on the level Σ2, the index set REC of the class of all recursive sets is on the level Σ3, the index set COFIN of all cofinite sets is also on the level Σ3 and the index set COMP of the class of all Turing-complete sets Σ4. These hierarchy levels are defined inductively, Σn+1 contains just all sets which are computably enumerable relative to Σn; Σ1 contains the computably enumerable sets. The index sets given here are even complete for their levels, that is, all the sets in these levels can be many-one reduced to the given index sets.
The program ofreverse mathematics asks which set-existence axioms are necessary to prove particular theorems of mathematics in subsystems ofsecond-order arithmetic. This study was initiated byHarvey Friedman and was studied in detail byStephen Simpson and others; in 1999, Simpson[18] gave a detailed discussion of the program. The set-existence axioms in question correspond informally to axioms saying that thepowerset of the natural numbers is closed under various reducibility notions. The weakest such axiom studied in reverse mathematics isrecursive comprehension, which states that the powerset of the naturals is closed under Turing reducibility.
A numbering is an enumeration of functions; it has two parameters,e andx and outputs the value of thee-th function in the numbering on the inputx. Numberings can be partial-computable although some of its members are total computable functions.Admissible numberings are those into which all others can be translated. AFriedberg numbering (named after its discoverer) is a one-one numbering of all partial-computable functions; it is necessarily not an admissible numbering. Later research dealt also with numberings of other classes like classes of computably enumerable sets. Goncharov discovered for example a class of computably enumerable sets for which the numberings fall into exactly two classes with respect to computable isomorphisms.
Post's problem was solved with a method called thepriority method; a proof using this method is called apriority argument. This method is primarily used to construct computably enumerable sets with particular properties. To use this method, the desired properties of the set to be constructed are broken up into an infinite list of goals, known asrequirements, so that satisfying all the requirements will cause the set constructed to have the desired properties. Each requirement is assigned to a natural number representing the priority of the requirement; so 0 is assigned to the most important priority, 1 to the second most important, and so on. The set is then constructed in stages, each stage attempting to satisfy one of more of the requirements by either adding numbers to the set or banning numbers from the set so that the final set will satisfy the requirement. It may happen that satisfying one requirement will cause another to become unsatisfied; the priority order is used to decide what to do in such an event.
Priority arguments have been employed to solve many problems in computability theory, and have been classified into a hierarchy based on their complexity.[12] Because complex priority arguments can be technical and difficult to follow, it has traditionally been considered desirable to prove results without priority arguments, or to see if results proved with priority arguments can also be proved without them. For example, Kummer published a paper on a proof for the existence of Friedberg numberings without using the priority method.
When Post defined the notion of a simple set as a c.e. set with an infinite complement not containing any infinite c.e. set, he started to study the structure of the computably enumerable sets under inclusion. This lattice became a well-studied structure. Computable sets can be defined in this structure by the basic result that a set is computable if and only if the set and its complement are both computably enumerable. Infinite c.e. sets have always infinite computable subsets; but on the other hand, simple sets exist but do not always have a coinfinite computable superset. Post[15] introduced already hypersimple and hyperhypersimple sets; later maximal sets were constructed which are c.e. sets such that every c.e. superset is either a finite variant of the given maximal set or is co-finite. Post's original motivation in the study of this lattice was to find a structural notion such that every set which satisfies this property is neither in the Turing degree of the computable sets nor in the Turing degree of the halting problem. Post did not find such a property and the solution to his problem applied priority methods instead; in 1991, Harrington and Soare[19] found eventually such a property.
Another important question is the existence of automorphisms in computability-theoretic structures. One of these structures is that one of computably enumerable sets under inclusion modulo finite difference; in this structure,A is belowB if and only if the set differenceB − A is finite.Maximal sets (as defined in the previous paragraph) have the property that they cannot be automorphic to non-maximal sets, that is, if there is an automorphism of the computably enumerable sets under the structure just mentioned, then every maximal set is mapped to another maximal set. In 1974, Soare[20] showed that also the converse holds, that is, every two maximal sets are automorphic. So the maximal sets form an orbit, that is, every automorphism preserves maximality and any two maximal sets are transformed into each other by some automorphism. Harrington gave a further example of an automorphic property: that of the creative sets, the sets which are many-one equivalent to the halting problem.
Besides the lattice of computably enumerable sets, automorphisms are also studied for the structure of the Turing degrees of all sets as well as for the structure of the Turing degrees of c.e. sets. In both cases, Cooper claims to have constructed nontrivial automorphisms which map some degrees to other degrees; this construction has, however, not been verified and some colleagues believe that the construction contains errors and that the question of whether there is a nontrivial automorphism of the Turing degrees is still one of the main unsolved questions in this area.[21][17]
The field ofKolmogorov complexity andalgorithmic randomness was developed during the 1960s and 1970s by Chaitin, Kolmogorov, Levin, Martin-Löf and Solomonoff (the names are given here in alphabetical order; much of the research was independent, and the unity of the concept of randomness was not understood at the time). The main idea is to consider auniversal Turing machineU and to measure the complexity of a number (or string)x as the length of the shortest inputp such thatU(p) outputsx. This approach revolutionized earlier ways to determine when an infinite sequence (equivalently, characteristic function of a subset of the natural numbers) is random or not by invoking a notion of randomness for finite objects. Kolmogorov complexity became not only a subject of independent study but is also applied to other subjects as a tool for obtaining proofs.There are still many open problems in this area.[d]
This branch of computability theory analyzed the following question: For fixedm andn with 0 < m < n, for which functionsA is it possible to compute for any differentn inputsx1, x2, ..., xn a tuple ofn numbersy1, y2, ..., yn such that at leastm of the equationsA(xk) =yk are true. Such sets are known as (m, n)-recursive sets. The first major result in this branch of computability theory is Trakhtenbrot's result that a set is computable if it is (m, n)-recursive for somem, n with 2m > n. On the other hand, Jockusch'ssemirecursive sets (which were already known informally before Jockusch introduced them 1968) are examples of a set which is (m, n)-recursive if and only if 2m < n + 1. There are uncountably many of these sets and also some computably enumerable but noncomputable sets of this type. Later, Degtev established a hierarchy of computably enumerable sets that are (1, n + 1)-recursive but not (1, n)-recursive. After a long phase of research by Russian scientists, this subject became repopularized in the west by Beigel's thesis on bounded queries, which linked frequency computation to the above-mentioned bounded reducibilities and other related notions. One of the major results was Kummer's cardinality theorem[22][23] which states that a setA is computable if and only if there is a Turing machine that givenn inputsx1, x2, ..., xn, returns at mostn outputs, one of which is the cardinality of {x1, x2, ..., xn}∩A (there are onlyn + 1 possible values of the cardinality: 0, ...,n).
This is the computability-theoretic branch of learning theory. It is based onE. Mark Gold's model of learning in the limit from 1967 and has developed since then more and more models of learning. The general scenario is the following: Given a classS of computable functions, is there a learner (that is, computable functional) which outputs for any input of the form (f(0), f(1), ..., f(n)) a hypothesis. A learnerM learns a functionf if almost all hypotheses are the same indexe off with respect to a previously agreed on acceptable numbering of all computable functions;M learnsS ifM learns everyf inS. Basic results are that all computably enumerable classes of functions are learnable while the class REC of all computable functions is not learnable. Many related models have been considered and also the learning of classes of computably enumerable sets from positive data is a topic studied from Gold's pioneering paper in 1967 onwards.
Computability theory includes the study of generalized notions of this field such asarithmetic reducibility,hyperarithmetical reducibility andα-recursion theory, as described by Sacks in 1990.[24] These generalized notions include reducibilities that cannot be executed by Turing machines but are nevertheless natural generalizations of Turing reducibility. These studies include approaches to investigate theanalytical hierarchy which differs from thearithmetical hierarchy by permitting quantification over sets of natural numbers in addition to quantification over individual numbers. These areas are linked to the theories of well-orderings and trees; for example the set of all indices of computable (nonbinary) trees without infinite branches is complete for level of the analytical hierarchy. Both Turing reducibility and hyperarithmetical reducibility are important in the field ofeffective descriptive set theory. The even more general notion ofdegrees of constructibility is studied inset theory.
Computability theory for digital computation is well developed. Computability theory is less well developed foranalog computation that occurs inanalog computers,analog signal processing,analog electronics,artificial neural networks and continuous-timecontrol theory, modelled bydifferential equations and continuousdynamical systems.[25][26] For example, models of computation such as theBlum–Shub–Smale machine model have formalized computation on the reals.
There are close relationships between the Turing degree of a set of natural numbers and the difficulty (in terms of thearithmetical hierarchy) of defining that set using afirst-order formula. One such relationship is made precise byPost's theorem. A weaker relationship was demonstrated byKurt Gödel in the proofs of hiscompleteness theorem andincompleteness theorems. Gödel's proofs show that the set of logical consequences of an effective first-order theory is acomputably 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.
Computability theory is also linked tosecond-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 ofreverse mathematics uses these subsystems to measure the non-computability inherent in well known mathematical theorems. In 1999, Simpson[18] discussed many aspects of second-order arithmetic and reverse mathematics.
The field ofproof theory includes the study of second-order arithmetic andPeano arithmetic, as well as 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 betotal.[27] For example, inprimitive recursive arithmetic any computable function that is provably total is actuallyprimitive recursive, whilePeano arithmetic proves that functions like theAckermann 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 byGoodstein's theorem.
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[13] 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 have begun to use this alternate terminology.[e] These researchers also use terminology such aspartial computable function andcomputably enumerable(c.e.) set instead ofpartial recursive function andrecursively enumerable(r.e.) set. Not all researchers have been convinced, however, as explained by Fortnow[28] and Simpson.[29]Some commentators argue that both the namesrecursion theory andcomputability theory fail to convey the fact that most of the objects studied in computability theory are not computable.[30]
In 1967, Rogers[31] has suggested that a key property of computability theory is that its results and structures should be invariant under computablebijections on the natural numbers (this suggestion draws on the ideas of theErlangen 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). According to Rogers, the sets of interest in computability theory are the noncomputable sets, partitioned into equivalence classes by computable bijections of the natural numbers.
The main professional organization for computability theory is theAssociation for Symbolic Logic, which holds several research conferences each year. The interdisciplinary research AssociationComputability in Europe (CiE) also organizes a series of annual conferences.
Kurt Gödel (1946):Tarski has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an interesting epistemological notion, i.e., one not depending on the formalism chosen.
To be more precise: a function of integers is computable in any formal system containing arithmetic if and only if it is computable in arithmetic, where a functionf is called computable inS if there is inS a computable term representingf.(NB. This volume also includes the 1946 paper byKurt Gödel (with commentary by Charles Parsons at pp. 144ff.). This 1990 edition has the cited footnote added by Gödel on p. 150 (which had also been added to Gödel's reprint inDavis' 1965 compilation).)
| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems (list) and paradoxes | |||||||||
| Logics |
| ||||||||
| Set theory |
| ||||||||
| Formal systems (list), language and syntax |
| ||||||||
| Proof theory | |||||||||
| Model theory | |||||||||
| Computability theory | |||||||||
| Related | |||||||||
