Turing degree

A Turing degree is an equivalence class of sets that can compute one another using oracle Turing machines. It measures a set’s computational unsolvability up to mutual Turing reducibility.

Turing reducibility: A set is Turing reducible to another if an oracle machine using the latter’s membership answers can decide the former. Mutual reducibility is the equivalence relation whose classes are Turing degrees.
Turing jump: An operation that maps a set to the halting problem for oracle machines using that set. The jump produces a strictly more powerful degree from any starting degree.
Computably enumerable degree: A Turing degree containing a computably enumerable set. The computably enumerable degrees form a heavily studied part of the degree structure.
Truth-table reducibility: A reducibility in which an algorithm’s oracle queries are determined in advance and combined by a computable truth table. It restricts oracle use more than Turing reducibility does.
Oracle Turing machine: A Turing machine equipped with an oracle that answers membership questions about a specified set in one step. It formalizes the computation used to compare sets by Turing reducibility.
Join of Turing degrees: The least upper bound of two Turing degrees, represented by the degree of the disjoint union of their sets. Joining degrees combines the computational information available from both.
Halting problem: The set of program-input pairs for which the program eventually halts. Its degree is the first Turing jump above the computable degree.
Many-one degree: An equivalence class of sets under mutual many-one reducibility. Many-one degrees distinguish sets that may share a Turing degree.
Computable set: A set whose membership can be decided by an algorithm that always halts. All computable sets belong to the least Turing degree.
Turing-incomparable sets: Sets for which neither is Turing reducible to the other. Their degrees are incomparable in the reducibility ordering.

Linked from 1 page

Post's theoremRelated: Iterated jumps identify increasingly powerful degrees associated with arithmetical levels.