12.2 Turing Degrees

Turing reducibility compares sets by computational power. If

then an oracle for $B$ is strong enough to decide $A$.

This comparison naturally groups sets into equivalence classes.

Two sets $A$ and $B$ have the same Turing degree if each can compute the other:

where:

A Turing degree is one equivalence class under $\equiv_T$. In simple terms, it is a level of computational power.

The Computable Degree

All computable sets have the same lowest degree.

This degree is written:

If $A$ is computable, then:

The empty set $\varnothing$ is used as a simple representative of this degree. An oracle for a computable set gives no extra power, because ordinary computation can already decide membership.

So:

means that $A$ is computable.

Noncomputable Degrees

A set that is not computable has a degree strictly above $\mathbf{0}$.

For such a set $A$:

This means $A$ contains information that ordinary algorithms cannot reproduce.

The halting problem gives the most important early example. Let:

The degree of $K$ is written:

This is called zero jump, or the Turing jump of $\mathbf{0}$.

The degree $\mathbf{0'}$ is strictly above the computable degree:

An oracle for $K$ can answer halting questions, so it gives strictly more power than ordinary computation.

Degrees as a Partial Order

Turing degrees are ordered by reducibility.

We write:

if:

This is well-defined because equivalent representatives have the same oracle power.

The order is reflexive:

It is transitive:

After quotienting by equivalence, it is also antisymmetric. So Turing degrees form a partial order.

Incomparability

A partial order does not require every pair to be comparable.

There may be degrees $\mathbf{a}$ and $\mathbf{b}$ such that neither can compute the other:

and:

Such degrees are called incomparable.

This is one reason the structure of Turing degrees is richer than a simple scale. Noncomputable problems do not line up in one chain from easy to hard. Some have different kinds of information.

Representatives and Degrees

A degree is an equivalence class, not a single set.

If:

then $A$ and $B$ may look very different, but they have the same computational strength.

For example, many different versions of the halting problem have degree $\mathbf{0'}$. They may use different encodings or ask slightly different halting questions, but they can compute each other.

So when we say “the degree of the halting problem,” we mean the whole class of sets equivalent to the halting problem.

The Turing Jump

The Turing jump is an operation that takes a degree and produces a strictly stronger one.

For a set $A$, define its jump $A'$ as the halting problem relative to oracle $A$:

Then:

The jump measures a higher level of computational difficulty. Starting from the computable degree, we get:

Here $\mathbf{0''}$ is the jump of $\mathbf{0'}$, and so on.

Each step gives access to a stronger halting oracle.

Intuition

A Turing degree measures what can be computed when a set is available as an oracle.

If $A$ has low degree, then $A$ gives limited extra information. If $A$ has high degree, then $A$ can solve more difficult decision problems.

But degrees do not form a single line. There are chains, jumps, incomparable pairs, minimal degrees, and many other structural phenomena.

Turing degrees give a precise language for saying that one undecidable problem is weaker, stronger, or incomparable with another.