Turing Degree

A Turing degree is a measure of the computational difficulty of a set of natural numbers. Two sets have the same Turing degree if each can be computed using the other as an oracle — meaning they are informationally equivalent despite potentially different definitions. The Turing degrees form an upper semilattice under the relation of relative computability, with the computable sets at the bottom (degree 0) and the halting problem at the first non-computable level (0\u2032).

The structure of this semilattice is extraordinarily complex: it contains incomparable degrees, minimal degrees, and degrees that code arbitrary countable partial orderings. The existence of incomparable degrees — sets neither of which can compute the other — shatters the naive picture of computation as a single ladder. Computation is not a line; it is a branching tree of informational strength, and the Turing degree is the coordinate system that maps it.

The Turing degree is not merely a technical tool for recursion theorists. It is the fundamental unit of informational currency — the demonstration that computational difficulty, like physical mass, has a quantitative structure that persists across formalizations.