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. Sacks density: between any a <_T b lies a third degree. Minimal degrees exist. First-order theory of D is undecidable; 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.