Turing degree
|
|
In computability theory, the Turing degree of a subset <math>X<math> of the natural numbers <math>\omega<math>, is the equivalence class consisting of all subsets of <math>\omega<math> equivalent to <math>X<math> under Turing reducibility. In other words, two sets of natural numbers have the same Turing degree when the question of whether a natural number belongs to one can be decided by a Turing machine having an oracle that can answer the question of whether a number belongs to the other, and vice versa. So the Turing degree measures precisely the computability or incomputability of <math>X<math>. Turing reducibility induces a partial order on the Turing degrees. The degree of a set <math>X<math> is denoted <math>\textbf{deg}(X)<math>. The least element in the partial order is <math>0 = \textbf{deg}(\emptyset)<math> and is the degree of all recursive sets (computable sets).
For each Turing degree <math>\textbf{d}<math> (say, to which a set <math>X<math> belongs), there is another degree, <math>\mathop{\textrm{TJ}}(\textbf{d})<math>, which is greater than <math>\textbf{d}<math>, constructed in the following way: choose (once and for all) a standard enumeration of all Turing machines having (the characteristic function of) <math>X<math> as an oracle, and form the set <math>K^X<math> of all <math>n<math> such that the <math>n<math>-th such machine halts (on the input <math>n<math>, but this doesn't matter very much). Then <math>X<math> is computable from this set <math>K^X<math> but the converse isn't true. We call <math>\mathop{\textrm{TJ}}(\textbf{d})<math> (which depends only on <math>\textbf{d}<math> and not on the choice of <math>X<math> having that Turing degree) the Turing jump of <math>\textbf{d}<math>. For example, <math>\mathop{\textrm{TJ}}(0)<math> is the Turing degree of the usual halting problem.
A recursively enumerable Turing degree (computably enumerable Turing degree) is one containing a recursively enumerable set (computably enumerable set). The recursively enumerable Turing degrees under the partial order induced by Turing reducibility form an upper semi-lattice, having <math>0<math> as smallest element and <math>\mathop{\textrm{TJ}}(0)<math> as greatest element, and are an object that has been much studied by the logic community. One of the famous problems associated with the recursively enumerable degrees, known as Post's problem, is whether there exists such a degree which is not equal to <math>0<math> nor <math>\mathop{\textrm{TJ}}(0)<math>. It is now known that the answer is positive (and much more is known).