Turing reduction

Remarks

Example: for every $B \subseteq \N$, the complement $\N \setminus B$ satisfies $\N \setminus B \le_T B$. The machine asks the oracle whether $x \in B$ and outputs the opposite answer.

Non-example: the halting problem $K$ satisfies $K \not\le_T \emptyset$. An oracle machine with the empty oracle computes only what an ordinary Turing machine computes, and $K$ is not a computable set.

The relation $\le_T$ is reflexive and transitive. A set $A$ satisfies $A \le_T \emptyset$ exactly when $A$ is computable. Every many-one reduction gives a Turing reduction. The converse fails: $\N \setminus K \le_T K$, but $\N \setminus K \not\le_m K$, since $K$ is computably enumerable and $\N \setminus K$ is not.