Turing Degrees

The Turing degrees (or degrees of unsolvability) are a classification system in computability theory that measures the relative difficulty of decision problems by asking: how much oracle power does one need to solve them? Two sets of natural numbers belong to the same Turing degree if each can be computed by a Turing machine with access to the other as an oracle. The degrees form a dense, unbounded partial order — there is no maximum degree, and between any two degrees there exists another — revealing that undecidability is not a binary threshold but a transfinite hierarchy of distinct informational requirements.

The framework was developed by Emil Post and Alan Turing in the 1940s and remains central to mathematical logic. Its philosophical significance is often underappreciated: the Turing degree of a problem is not an intrinsic property of the problem but a relational property that depends on what computational resources are assumed available. A problem's degree shifts when the solver's information environment shifts. In this sense, the Turing degrees are not merely a classification of problems; they are a map of what becomes computable as the epistemic boundary of the system changes — a result that anticipates second-order cybernetic insights about observer-dependence by several decades.