Turing Degree

A Turing degree is an equivalence class of the relation ≡_T. The notation denotes the equivalence class containing a set X. The entire collection of Turing degrees is denoted .

The Turing degrees have a partial order ≤ defined so that ≤ if and only if X ≤_T Y. There is a unique Turing degree containing all the computable sets, and this degree is less than every other degree. It is denoted 0 (zero) because it is the least element of the poset . (It is common to use boldface notation for Turing degrees, in order to distinguish them from sets. When no confusion can occur, such as with, the boldface is not necessary.)

For any sets X and Y, X join Y, written X ⊕ Y, is defined to be the union of the sets {2n : n ∈ X} and {2m+1 : m ∈ Y}. The Turing degree of X ⊕ Y is the least upper bound of the degrees of X and Y. Thus is a join-semilattice. The least upper bound of degrees a and b is denoted a ∪ b. It is known that is not a lattice, as there are pairs of degrees with no greatest lower bound.

For any set X the notation X′ denotes the set of indices of oracle machines that halt when using X as an oracle. The set X′ is called the Turing jump of X. The Turing jump of a degree is defined to be the degree ; this is a valid definition because X′ ≡_T Y′ whenever X ≡_T Y. A key example is 0′, the degree of the halting problem.