Relative Computability

Relative computability is the study of computability when computational power is augmented by access to a fixed oracle — a hypothetical device that resolves some otherwise-undecidable question at zero cost. The central objects are the Turing degrees (or degrees of unsolvability), which classify sets of natural numbers by their relative computational difficulty: two sets belong to the same degree if each is oracle-computable from the other. The degrees form a dense partial order with no maximum, revealing that undecidability is not a single cliff but a transfinite hierarchy of distinct difficulty levels. Relative computability is foundational for understanding the fine structure of the arithmetical hierarchy and for complexity theory's relativized separations.