HOME

TheInfoList



OR:

Computability theory, also known as recursion theory, is a branch of
mathematical logic Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
,
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized
computability Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...
and definability. In these areas, computability theory overlaps with
proof theory Proof theory is a major branchAccording to Wang (1981), pp. 3–4, proof theory is one of four domains mathematical logic, together with model theory, axiomatic set theory, and recursion theory. Jon Barwise, Barwise (1978) consists of four correspo ...
and
effective descriptive set theory Effective descriptive set theory is the branch of descriptive set theory dealing with sets of reals having lightface definitions; that is, definitions that do not require an arbitrary real parameter (Moschovakis 1980). Thus effective descriptive ...
. Basic questions addressed by computability theory include: * What does it mean for a function on the
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal n ...
s to be computable? * How can noncomputable functions be classified into a hierarchy based on their level of noncomputability? 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 of subrecursive hierarchies, formal methods, and
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...
s.


Introduction

Computability theory originated in the 1930s, with work of
Kurt Gödel Kurt Friedrich Gödel ( , ; April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher. Considered along with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel had an imme ...
, Alonzo Church, Rózsa Péter,
Alan Turing Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...
, Stephen Kleene, and Emil Post. The fundamental results the researchers obtained established Turing 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" and "Turing's thesis". Nowadays these are often considered as a single hypothesis, the
Church–Turing thesis In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a thesis about the nature of comp ...
, which states that any function that is computable by an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
is a computable function. Although initially skeptical, by 1946 Gödel argued in favor of this thesis: With a definition of effective calculation came the first proofs that there are problems in mathematics that cannot be effectively decided. In 1936, Church and Turing were inspired by techniques used by Gödel to prove his incompleteness theorems - in 1931, Gödel independently demonstrated that the 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 in
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
have been shown to be undecidable after these initial examples were established. In 1947, Markov and Post published independent papers showing that the
word problem for semigroups A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no consen ...
cannot be effectively decided. Extending this result,
Pyotr Novikov Pyotr Sergeyevich Novikov (russian: Пётр Серге́евич Но́виков; 15 August 1901, Moscow, Russian Empire – 9 January 1975, Moscow, Soviet Union) was a Soviet mathematician. Novikov is known for his work on combinatorial proble ...
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 Yuri Vladimirovich Matiyasevich, (russian: Ю́рий Влади́мирович Матиясе́вич; born 2 March 1947 in Leningrad) is a Russian mathematician and computer scientist. He is best known for his negative solution of Hilbert's t ...
proved (using results of Julia Robinson)
Matiyasevich's theorem In mathematics, a Diophantine equation is an equation of the form ''P''(''x''1, ..., ''x'j'', ''y''1, ..., ''y'k'') = 0 (usually abbreviated ''P''(', ') = 0) where ''P''(', ') is a polynomial with integer coefficients, where ''x''1, ..., '' ...
, which implies that
Hilbert's tenth problem Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900. It is the challenge to provide a general algorithm which, for any given Diophantine equation (a polynomial equat ...
has no effective solution; this problem asked whether there is an effective procedure to decide whether a
Diophantine equation In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a c ...
over the integers has a solution in the integers. The
list of undecidable problems In computability theory, an undecidable problem is a type of computational problem that requires a yes/no answer, but where there cannot possibly be any computer program that always gives the correct answer; that is, any possible program would some ...
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'' covers many of the known results in this field.


Turing computability

The main form of computability studied in computability theory was introduced by Turing in 1936. A set of natural numbers is said to be a '' computable set'' (also called a ''decidable'', ''recursive'', or ''Turing computable'' set) if there is a
Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
that, 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 natural numbers to natural numbers is a ''(Turing)
computable Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...
,'' or ''recursive function'' if there is a Turing machine that, 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; 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 of functions by Gödel led to the traditional name ''recursive'' for sets and functions computable by a Turing machine. The word ''decidable'' stems from the German word which was used in the original papers of Turing and others. In contemporary use, the term "computable function" has various definitions: according to
Nigel J. Cutland Nigel J. Cutland is Professor of Mathematics at the University of York. His main fields of interest are non-standard analysis, Loeb spaces, and applications in probability and stochastic analysis. He was Editor-in-Chief of ''Logic and Analysis'' ...
, it is a partial recursive function (which can be undefined for some inputs), while according to
Robert I. Soare Robert Irving Soare is an American mathematician. He is the Paul Snowden Russell Distinguished Service Professor of Mathematics and Computer Science at the University of Chicago, where he has been on the faculty since 1967. He proved, together wi ...
it is a total recursive (equivalently, general recursive) function. This article follows the second of these conventions. In 1996, Soare gave additional comments about the terminology. Not every set of natural numbers is computable. The
halting problem In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...
, 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 In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural number ...
Turing machines, and thus only countably many computable sets, but according to the Cantor's theorem, there are
uncountably many In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal numb ...
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 a '' computably enumerable (c.e.) set'', which is a set that can be enumerated by a Turing machine (other terms for computably enumerable include ''recursively enumerable'' and ''semidecidable''). 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.


Areas of research

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.


Relative computability and the Turing degrees

Computability theory in mathematical logic has traditionally focused on ''relative computability'', a generalization of Turing computability defined using
oracle Turing machine In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a s ...
s, introduced by Turing in 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 only 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 a Turing machine without an oracle cannot. Informally, a set of natural numbers ''A'' is ''
Turing reducible In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to ...
'' 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 also said to be (''relatively'') ''computable from'' ''B'' and ''recursive in'' ''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 natural examples of sets that are not computable, including many different sets that encode variants of the
halting problem In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...
, have two properties in common: #They are computably enumerable, and #Each can be translated into any other via a
many-one reduction In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem L_1 into instances of a second decision problem L_2 where the instan ...
. That is, given such sets ''A'' and ''B'', there is a total computable function ''f'' such that ''A'' = . These sets are said to be ''many-one equivalent'' (or ''m-equivalent''). Many-one reductions are "stronger" than Turing reductions: if a set ''A'' is many-one reducible to a set ''B'', then ''A'' is Turing reducible to ''B'', 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 sets ''A'' and ''B'' such that ''A'' is Turing reducible to ''B'' but not many-one reducible to ''B''. 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 asked whether ''every'' computably enumerable set is either computable or Turing 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 the
simple Simple or SIMPLE may refer to: *Simplicity, the state or quality of being simple Arts and entertainment * ''Simple'' (album), by Andy Yorke, 2008, and its title track * "Simple" (Florida Georgia Line song), 2018 * "Simple", a song by Johnn ...
, 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 as '' Post'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 function ''f'' which dominates every computable function ''g'' in the sense that there is a constant ''c'' depending on ''g'' such that ''g(x) < f(x)'' for all ''x > c''; ''random degrees'' containing
algorithmically random set Intuitively, an algorithmically random sequence (or random sequence) is a Sequence#Infinite sequences in theoretical computer science, sequence of binary digits that appears random to any algorithm running on a (prefix-free or not) universal Turi ...
s; ''1-generic'' degrees of 1-generic sets; and the degrees below the halting problem of
limit-computable In computability theory, a function is called limit computable if it is the limit of a uniformly computable sequence of functions. The terms computable in the limit, limit recursive and recursively approximable are also used. One can think of lim ...
sets. The study of arbitrary (not necessarily computably enumerable) Turing degrees involves the study of the Turing jump. Given a set ''A'', the ''
Turing jump In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine w ...
'' of ''A'' is a set of natural numbers encoding a solution to the halting problem for oracle Turing machines running with oracle ''A''. 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 the arithmetical 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 states that the function mapping a degree ''x'' to the degree of its Turing jump is definable in the partial order of the Turing degrees. A survey by Ambos-Spies and Fejer gives an overview of this research and its historical progression.


Other reducibilities

An ongoing area of research in computability theory studies reducibility relations other than Turing reducibility. Post introduced several ''strong 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: : One-one reducibility: ''A'' is ''one-one reducible'' (or ''1-reducible'') to ''B'' if there is a total computable
injective function In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
''f'' such that each ''n'' is in ''A'' if and only if ''f''(''n'') is in ''B''. : Many-one reducibility: This is essentially one-one reducibility without the constraint that ''f'' be injective. ''A'' is ''many-one reducible'' (or ''m-reducible'') to ''B'' if there is a total computable function ''f'' such that each ''n'' is in ''A'' if and only if ''f''(''n'') is in ''B''. : Truth-table reducibility: ''A'' is truth-table reducible to ''B'' if ''A'' is Turing reducible to ''B'' via an oracle Turing machine that computes a total function regardless of the oracle it is given. Because of compactness of Cantor space, this is equivalent to saying that the reduction presents a single list of questions (depending only on the input) to the oracle simultaneously, and then having seen their answers is able to produce an output without asking additional questions regardless of the oracle's answer to the initial queries. Many variants of truth-table reducibility have also been studied. Further reducibilities (positive, disjunctive, conjunctive, linear and their weak and bounded versions) are discussed in the article Reduction (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 are
arithmetical reducibility In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy (after mathematicians Stephen Cole Kleene and Andrzej Mostowski) classifies certain Set (mathematics), sets based on the complexity of formul ...
and
hyperarithmetical reducibility In recursion theory, hyperarithmetic theory is a generalization of Computable function, Turing computability. It has close connections with definability in second-order arithmetic and with weak systems of set theory such as Kripke–Platek set theo ...
. These reducibilities are closely connected to definability over the standard model of arithmetic.


Rice's theorem and the arithmetical hierarchy

Rice Rice is the seed of the grass species ''Oryza sativa'' (Asian rice) or less commonly ''Oryza glaberrima ''Oryza glaberrima'', commonly known as African rice, is one of the two domesticated rice species. It was first domesticated and grown i ...
showed that for every nontrivial class ''C'' (which contains some but not all c.e. sets) the index set ''E'' = has the property that either the
halting problem In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...
or its complement is many-one reducible to ''E'', that is, can be mapped using a
many-one reduction In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem L_1 into instances of a second decision problem L_2 where the instan ...
to ''E'' (see Rice'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 the arithmetical 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.


Reverse mathematics

The program of '' reverse mathematics'' asks which set-existence axioms are necessary to prove particular theorems of mathematics in subsystems of second-order arithmetic. This study was initiated by Harvey Friedman and was studied in detail by
Stephen Simpson Stephen Simpson (born 8 January 1984) is a South African-American professional racing driver currently competing in the IMSA WeatherTech SportsCar Championship and previously in the A1 Grand Prix, Champ Car Atlantic Championship and the Indy Pr ...
and others; in 1999, Simpson gave a detailed discussion of the program. The set-existence axioms in question correspond informally to axioms saying that the
powerset In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is postu ...
of the natural numbers is closed under various reducibility notions. The weakest such axiom studied in reverse mathematics is ''recursive comprehension'', which states that the powerset of the naturals is closed under Turing reducibility.


Numberings

A numbering is an enumeration of functions; it has two parameters, ''e'' and ''x'' and outputs the value of the ''e''-th function in the numbering on the input ''x''. Numberings can be partial-computable although some of its members are total computable functions.
Admissible numbering In computability theory, admissible numberings are enumerations (Numbering (computability theory), numberings) of the set of partial computable functions that can be converted ''to and from'' the standard numbering. These numberings are also called ...
s are those into which all others can be translated. A
Friedberg numbering In computability theory, a Friedberg numbering is a numbering There are many different numbering schemes for assigning nominal numbers to entities. These generally require an agreed set of rules, or a central coordinator. The schemes can be consid ...
(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.


The priority method

Post's problem was solved with a method called the ''priority method''; a proof using this method is called a ''priority 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 as ''requirements'', 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. 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.


The lattice of computably enumerable sets

When Post defined the notion of a simple set as an 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 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 found eventually such a property.


Automorphism problems

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 below ''B'' if and only if the set difference ''B'' − ''A'' is finite.
Maximal set In recursion theory, the mathematical theory of computability, a maximal set is a coinfinite recursively enumerable subset ''A'' of the natural numbers such that for every further recursively enumerable subset ''B'' of the natural numbers, either ' ...
s (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 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.


Kolmogorov complexity

The field of Kolmogorov complexity and
algorithmic randomness Intuitively, an algorithmically random sequence (or random sequence) is a sequence of binary digits that appears random to any algorithm running on a (prefix-free or not) universal Turing machine. The notion can be applied analogously to sequenc ...
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 a universal Turing machine ''U'' and to measure the complexity of a number (or string) ''x'' as the length of the shortest input ''p'' such that ''U''(''p'') outputs ''x''. 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. For that reason, a recent research conference in this area was held in January 2007 and a list of open problems is maintained by Joseph Miller and André Nies.


Frequency computation

This branch of computability theory analyzed the following question: For fixed ''m'' and ''n'' with 0 < ''m'' < ''n'', for which functions ''A'' is it possible to compute for any different ''n'' inputs ''x''1, ''x''2, ..., ''xn'' a tuple of ''n'' numbers ''y1, y2, ..., yn'' such that at least ''m'' of the equations ''A''(''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 some ''m'', ''n'' with 2''m'' > ''n''. On the other hand, Jockusch's
semirecursive In mathematics and theoretical computer science, the semi-membership problem for a set is the problem of deciding which of two possible elements is logically more likely to belong to that set; alternatively, given two elements of which at least one ...
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 2''m'' < ''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 Theory which states that a set ''A'' is computable if and only if there is an ''n'' such that some algorithm enumerates for each tuple of ''n'' different numbers up to ''n'' many possible choices of the cardinality of this set of ''n'' numbers intersected with ''A''; these choices must contain the true cardinality but leave out at least one false one.


Inductive inference

This is the computability-theoretic branch of learning theory. It is based on
E. Mark Gold E. Mark Gold (often written "E Mark Gold" without a dot, born 1936 in Los Angeles) is an American physicist, mathematician, and computer scientist. He became well known for his article ''Language identification in the limit'' which pioneered a fo ...
'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 class ''S'' 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 learner ''M'' learns a function ''f'' if almost all hypotheses are the same index ''e'' of ''f'' with respect to a previously agreed on acceptable numbering of all computable functions; ''M'' learns ''S'' if ''M'' learns every ''f'' in ''S''. 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.


Generalizations of Turing computability

Computability theory includes the study of generalized notions of this field such as arithmetic reducibility,
hyperarithmetical reducibility In recursion theory, hyperarithmetic theory is a generalization of Computable function, Turing computability. It has close connections with definability in second-order arithmetic and with weak systems of set theory such as Kripke–Platek set theo ...
and α-recursion theory, as described by Sacks in 1990. 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 the analytical hierarchy which differs from the arithmetical 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 \Pi^1_1 of the analytical hierarchy. Both Turing reducibility and hyperarithmetical reducibility are important in the field of
effective descriptive set theory Effective descriptive set theory is the branch of descriptive set theory dealing with sets of reals having lightface definitions; that is, definitions that do not require an arbitrary real parameter (Moschovakis 1980). Thus effective descriptive ...
. The even more general notion of degrees of constructibility is studied in
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
.


Continuous computability theory

Computability theory for digital computation is well developed. Computability theory is less well developed for
analog computation An analog computer or analogue computer is a type of computer that uses the continuous variation aspect of physical phenomena such as electrical, mechanical, or hydraulic quantities (''analog signals'') to model the problem being solved. I ...
that occurs in analog computers, analog signal processing, analog electronics,
neural network A neural network is a network or circuit of biological neurons, or, in a modern sense, an artificial neural network, composed of artificial neurons or nodes. Thus, a neural network is either a biological neural network, made up of biological ...
s and continuous-time
control theory Control theory is a field of mathematics that deals with the control of dynamical systems in engineered processes and machines. The objective is to develop a model or algorithm governing the application of system inputs to drive the system to a ...
, modelled by
differential equation In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, an ...
s and continuous
dynamical system In mathematics, a dynamical system is a system in which a Function (mathematics), function describes the time dependence of a Point (geometry), point in an ambient space. Examples include the mathematical models that describe the swinging of a ...
s. For example, models of computation such as the
Blum–Shub–Smale machine In computation theory, the Blum–Shub–Smale machine, or BSS machine, is a model of computation introduced by Lenore Blum, Michael Shub and Stephen Smale, intended to describe computations over the real numbers. Essentially, a BSS machine is a Ra ...
model have formalized computation on the reals.


Relationships between definability, proof 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 Kurt Friedrich Gödel ( , ; April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher. Considered along with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel had an imme ...
in the proofs of his
completeness theorem Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...
and
incompleteness theorem Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies t ...
s. Gödel's proofs show that the set of logical consequences of an effective first-order theory is a
computably enumerable set In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the ...
, 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 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 non-computability inherent in well known mathematical theorems. In 1999, Simpson discussed many aspects of second-order arithmetic and reverse mathematics. The field of
proof theory Proof theory is a major branchAccording to Wang (1981), pp. 3–4, proof theory is one of four domains mathematical logic, together with model theory, axiomatic set theory, and recursion theory. Jon Barwise, Barwise (1978) consists of four correspo ...
includes the study of second-order arithmetic and
Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
, 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 be
total Total may refer to: Mathematics * Total, the summation of a set of numbers * Total order, a partial order without incomparable pairs * Total relation, which may also mean ** connected relation (a binary relation in which any two elements are comp ...
. For example, in
primitive recursive arithmetic Primitive recursive arithmetic (PRA) is a quantifier-free formalization of the natural numbers. It was first proposed by Norwegian mathematician , reprinted in translation in as a formalization of his finitist conception of the foundations of ar ...
any computable function that is provably total is actually
primitive recursive In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...
, while
Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
proves that functions like the
Ackermann function In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total ...
, 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

The field of mathematical logic dealing with computability and its generalizations has been called "recursion theory" since its early days.
Robert I. Soare Robert Irving Soare is an American mathematician. He is the Paul Snowden Russell Distinguished Service Professor of Mathematics and Computer Science at the University of Chicago, where he has been on the faculty since 1967. He proved, together wi ...
, a prominent researcher in the field, has proposed 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. 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 computability theory are not computable. In 1967, Rogers has suggested that a key property of computability theory is that its results and structures should be invariant under computable
bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
s 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). 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.


Professional organizations

The main professional organization for computability theory is the ''
Association for Symbolic Logic The Association for Symbolic Logic (ASL) is an international organization of specialists in mathematical logic and philosophical logic. The ASL was founded in 1936, and its first president was Alonzo Church. The current president of the ASL is ...
'', which holds several research conferences each year. The interdisciplinary research Association ''
Computability in Europe The Association Computability in Europe (ACiE) is an international organization of mathematicians, logicians, computer scientists, philosophers, theoretical physicists and others interested in new developments in computability and in their underly ...
'' (''CiE'') also organizes a series of annual conferences.


See also

*
Recursion (computer science) In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves ...
*
Computability logic Computability logic (CoL) is a research program and mathematical framework for redeveloping logic as a systematic formal theory of computability, as opposed to classical logic which is a formal theory of truth. It was introduced and so named by G ...
* Transcomputational problem


Notes


References


Further reading

; Undergraduate level texts * * ; Advanced texts * * * * * ; Survey papers and collections * ; Research papers and collections * * *

* * * * Reprinted in .


External links


Association for Symbolic Logic homepage

Computability in Europe homepage


* ttp://www.comp.nus.edu.sg/~fstephan/learning.ps German language lecture notes on inductive inference {{Mathematical logic C