Editing Computability theory (section)

===Relative computability and the Turing degrees===
{{Main|Turing reduction|Turing degree}}

Computability theory in mathematical logic has traditionally focused on ''relative computability'', a generalization of Turing computability defined using [[oracle Turing machine]]s, introduced by Turing in 1939.<ref name="Turing_1939"/> An oracle Turing machine is a hypothetical device which, in addition to performing the actions of a regular Turing machine, is able to ask questions of an ''oracle'', which is a particular set of natural numbers. The oracle machine may 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]]'' 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]], have two properties in common:
#They are [[recursively enumerable|computably enumerable]], and
#Each can be translated into any other via a [[many-one reduction]]. That is, given such sets ''A'' and ''B'', there is a total computable function ''f'' such that ''A'' = {''x'' : ''f''(''x'') ∈ ''B''}. 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<ref name="Post_1944"/> asked whether ''every'' computably enumerable set is either computable or [[Turing degree#Turing equivalence|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 set|simple]], [[hypersimple set|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) &lt; f(x)'' for all ''x &gt; c''; ''random degrees'' containing [[algorithmically random set]]s; ''1-generic'' degrees of 1-generic sets; and the degrees below the halting problem of [[limiting recursive|limit-computable]] 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]]'' 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<ref name="Shore-Slaman_1999"/> 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<ref name="Ambos-Spies-Fejer_2006"/> gives an overview of this research and its historical progression.