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
′	U+2032	Prime / Jump	Relativized halting problem
∨	U+2228	Join	Least upper bound of two degrees
⊕	U+2295	Circled plus / Effective join	Disjoint union of the underlying sets
↓	U+2193	Downwards arrow / Convergence	Oracle computation halts
<	U+003C	Less-than	Strict reducibility
≤_T	—	Turing reducibility	Computable with oracle
≡_T	—	Turing equivalence	Same degree
≤_m	—	Many-one reducibility	Strongest of the three
≤_tt	—	Truth-table reducibility	Intermediate strength
0	—	Zero degree	The computable sets
D	—	Degree structure	Upper semilattice of all Turing degrees
R	—	c.e. degrees	The substructure inside [0, 0′]

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. D is only an upper semilattice: joins exist by the effective disjoint union, but there are pairs of degrees with no greatest lower bound, so meets are unavailable and the algebra is one-sided. Turing reducibility places no bound on oracle use, so every decidable set has degree 0 whatever its cost and the whole of complexity theory is outside the classification — the polynomial-time reducibilities are a separate structure with different theorems. Because Th(D) is recursively isomorphic to second-order arithmetic, no classification of D is possible and embeddability results carry little information, since every countable partial order embeds. Whether D is rigid is open; what is known, by Slaman and Woodin, is that its automorphism group is countable and that every automorphism is the identity on the cone above 0″. Nothing in the subject exhibits its objects: minimal, 1-generic and incomparable degrees are produced by forcing with trees or by priority, and no naturally arising decision problem has ever been shown to have an intermediate degree — the natural undecidable problems all land on 0′ or another jump iterate.