Degrees of Unsolvability

The degrees of unsolvability, also called Turing degrees, are a classification of computational problems by their relative information content, introduced by Emil Post and developed into a systematic theory by Post, Stephen Kleene, and later researchers in computability theory. Two problems have the same Turing degree if each can be solved given an oracle for the other — that is, if they are computationally equivalent relative to external information. The resulting structure is an upper semilattice with a minimum degree 0 (the decidable problems) and a maximum degree 0′ (the halting problem), but the space between is rich, complex, and still not fully understood.

Post's central insight was that undecidability is not a binary condition but a graduated landscape. Some problems are strictly harder than others; some are incomparable. The study of this landscape — which degrees are realized by recursively enumerable sets, how the degrees are distributed, and what algebraic properties the structure possesses — became one of the deepest research programs in mathematical logic. The field has produced independence results, forcing arguments, and connections to algorithmic randomness that continue to surprise.