Turing degree
In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.
The concept of Turing degree is fundamental in computability theory, where sets of natural numbers are often regarded as decision problems.
Furthermore, the Turing degrees are partially ordered, so that if the Turing degree of a set X is less than the Turing degree of a set Y, then any (possibly noncomputable) procedure that correctly decides whether numbers are in Y can be effectively converted to a procedure that correctly decides whether numbers are in X.
It is in this sense that the Turing degree of a set corresponds to its level of algorithmic unsolvability.
The Turing degrees have been an area of intense research since then.
A set X is said to be Turing reducible to a set Y if there is an oracle Turing machine that decides membership in X when given an oracle for membership in Y.
The entire collection of Turing degrees is denoted
The Turing degrees have a partial order ≤ defined so that [X] ≤ [Y] if and only if X ≤T Y.
(It is common to use boldface notation for Turing degrees, in order to distinguish them from sets.
is not a lattice, as there are pairs of degrees with no greatest lower bound.
A great deal of research has been conducted into the structure of the Turing degrees.
One general conclusion that can be drawn from the research is that the structure of the Turing degrees is extremely complicated.
is r.e..[3] Additionally, there is Shoenfield's limit lemma, a set A satisfies
This problem was solved independently by Friedberg and Muchnik in the 1950s, who showed that these intermediate r.e.
The priority method is now the main technique for establishing results about r.e.
set X is to list a countable sequence of requirements that X must satisfy.
set X between 0 and 0′ it is enough to satisfy the requirements Ae and Be for each natural number e, where Ae requires that the oracle machine with index e does not compute 0′ from X and Be requires that the Turing machine with index e (and no oracle) does not compute X.
At each stage, numbers may be put into X or forever (if not injured) prevented from entering X in an attempt to satisfy requirements (that is, force them to hold once all of X has been enumerated).
At the start of stage n, let Tn be the output (binary) tape, identified with the set of cell indices where we placed 1 so far (so X=∪n Tn; T0=∅); and let Pn(m) be the priority for not outputting 1 at location m; P0(m)=∞.
X is noncomputable since otherwise a Turing machine could halt on Y iff Y\X is nonempty, contradicting the construction since X excludes some priority i cells for arbitrarily large i; and X is simple because for each i the number of priority i cells is finite.
