12.2 Turing Degrees
12.2 Turing Degrees Turing reducibility compares sets by computational power. If $$ A \leq_T B $$ 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: $$ A \equiv_T B $$ where: $$ A \leq_T B \quad \text{and} \quad B \leq_T A $$ A Turing...