Turing Degrees

Origin. Turing (1939) introduced oracle machines; Post, Kleene developed degrees of unsolvability. Structure of relative computability. Measures how uncomputable a set is.

Models. A ≤_T B when A is computable given an oracle for B. Degrees are equivalence classes under mutual reducibility. They form an upper semilattice ordered by relative computability.

Formalism.

Oracle machine: Turing machine with queries to an oracle set B. Computes relative to B.

Turing reducibility: A ≤_T B iff A computable by an oracle machine with oracle B. A ≡_T B iff A ≤_T B and B ≤_T A.

Degree structure D: Degrees = ≡_T classes. Upper semilattice: least element 0 (the computable sets). Join a ∨ b via A ⊕ B (disjoint union).

Jump operator: A′ = halting problem relative to A = {e : φ_e^A(e)↓}. A <_T A′ strictly. Monotone.

Jump hierarchy: 0 <_T 0′ <_T 0″ <_T ... 0′ ≡_T the halting set K.

Reducibility strength: Stronger: many-one ≤_m, truth-table ≤_tt. ≤_m ⟹ ≤_tt ⟹ ≤_T.

Symbols.

Symbol	Unicode	Name	Meaning
≤_T	—	Turing reducible	Computable with oracle
≡_T	—	Turing equivalent	Same degree
′	U+2032	Jump	Relativized halting
∨	U+2228	Join	Least upper bound
0	—	Zero degree	Computable sets

Metatheory. No greatest degree. D is not dense: Spector (1956) constructed minimal degrees, a degree m > 0 with nothing strictly between 0 and m, which refutes density outright. Sacks' density theorem (1964) is a theorem about the computably enumerable degrees R, not about D — for c.e. degrees a <_T b there is a c.e. degree c with a <_T c <_T b. The two facts are not in tension because they are about different structures, and conflating them makes D look dense when its most famous local feature is that it is not. First-order theory of D is undecidable — Simpson (1977) showed it is recursively isomorphic to second-order arithmetic — and every countable partial order embeds.

Applies to. Classification of unsolvable problems. Reverse mathematics. Effective algebra. Relative computability analysis.

Limitations. Highly abstract, non-constructive constructions. Priority arguments are technically demanding. Degree theory says little about feasibility.