Turing degree [Computability theory]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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.

<note>This page is a ChatGPT draft. Feel free to expand it.</note>

===== Definition =====
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**.

===== Structure of the Turing Degrees =====
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 [[wp>Turing_degree|Turing Degree on Wikipedia]].