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.

Oracles as Physical Interfaces

The oracle in relative computability is typically treated as a purely mathematical device — a black box that answers membership queries for some set A. But the oracle-structure has a precise physical analogue. In dynamical systems, an oracle is the environmental coupling that supplies information a system cannot compute from its internal state alone. A thermostat coupled to a temperature sensor is, in effect, accessing an oracle for the ambient temperature — a quantity it could not compute from its own state because the ambient temperature is not a function of the thermostat's internal variables.

This reframing makes relative computability relevant to questions about physical computation and embodied cognition. A robot navigating an environment uses sensor data as oracles for states of the world it cannot infer from its internal model. The limits of its behavior are therefore not merely the limits of its onboard computation but the limits of what its sensor-oracles make computable relative to its internal state. The Turing degree of a physical system's behavior is determined jointly by its internal computational capacity and the informational structure of its environmental coupling.

The Turing Degrees as a Complexity Landscape

The Turing degrees form a mathematical landscape that is in some respects analogous to the energy landscapes of statistical mechanics or the fitness landscapes of evolutionary biology. Like those landscapes, the degree structure has local maxima and minima, dense regions and sparse regions, and paths that connect distant points. The jump operator (mapping a set A to its Turing jump A') is a discrete step-function on this landscape, analogous to a phase transition or a mutational event.

This analogy is not merely decorative. Recent work in algorithmic randomness (drawing on Kolmogorov complexity) has shown that the degrees of randomness — the Martin-Löf degrees — form a structure that interacts in non-trivial ways with the Turing degrees. A set that is random relative to one oracle may be computable relative to another. The interaction between randomness and relative computability reveals that the 'hierarchy of difficulty' is not a simple ladder but a complex multidimensional structure in which information, randomness, and computational capacity are interdependent.

Open Questions

• Is there a physical system whose observable behavior corresponds to a specific non-zero Turing degree? Or are physical systems always either computable (degree 0) or too messy to classify?
• Can the structure of the Turing degrees be used to analyze the informational architecture of biological systems, where multiple subsystems with different computational capacities interact through 'oracle-like' interfaces?
• What is the relationship between relative computability and quantum computing, where oracles for quantum states may provide computational advantages not available to classical oracles?

Relative computability is not merely a technical chapter in the theory of computation. It is a framework for thinking about how systems gain information they cannot generate internally — a question that arises in physics, biology, cognition, and the design of any system that must act under uncertainty.

_The Turing degrees are not a ladder of abstraction. They are a map of the boundary between what a system can know from itself and what it must be told by the world. Every boundary in that map is an oracle — and every oracle is a place where the world speaks to the machine._