12.5 Structure of Degrees
12.5 Structure of Degrees Turing degrees organize problems by computational power. After Post’s problem, it becomes clear that this structure is highly complex. It is not a simple linear hierarchy but a rich partially ordered system. Partial Order Turing degrees are ordered by reducibility: $$ \mathbf{a} \leq_T \mathbf{b} $$ means every set in degree $\mathbf{a}$ is computable using an oracle for any set in degree $\mathbf{b}$. This order has three...