Turing degree

The concept of Turing degree is fundamental in computability theory and provides a way to classify the relative complexity of undecidable problems. Two sets of natural numbers have the same Turing degree if they are Turing equivalent, meaning each can be computed from the other using a Turing machine with an oracle for the set.

A set of natural numbers \( A \) has a Turing degree \( \deg(A) \), which represents the equivalence class of all sets Turing equivalent to \( A \). Formally, given two sets \( A \) and \( B \), we say that:

$$ A \leq_T B $$

if there exists an oracle Turing machine that can decide membership in \( A \) when given access to an oracle for \( B \). If \( A \leq_T B \) and \( B \leq_T A \), then \( A \) and \( B \) are Turing equivalent, written as \( A \equiv_T B \), meaning they belong to the same Turing degree.

The set of all Turing degrees, ordered by \( \leq_T \), forms an upper semilattice:

• There is a least degree, denoted \( \mathbf{0} \), containing all computable sets.
• There exist intermediate degrees, which are strictly between \( \mathbf{0} \) and the degree of the Halting problem.
• The join of two degrees \( \mathbf{a} \) and \( \mathbf{b} \) is the degree of the set \( A \oplus B \) (the disjoint union of \( A \) and \( B \)).
• The structure is highly complex and lacks a maximal element.

For more details, see Turing Degree on Wikipedia.