View source for Turing reducibility

A relation between sets of natural numbers.  We say that $A$ is Turing reducible to $B$, $A \le_{\mathrm{T}} B$, if there is a [[Turing machine]] for the decision problem $x \in A$ given an auxiliary tape which encodes the answers to all questions $y \in B$.  Such a tape is often described as an "oracle" or "black box" for the problem of membership of $B$.  This defines a [[pre-order]] on sets of natural numbers:Turing reduction may also be regarded as a relation between functions on natural numbers: in this case, the [[characteristic function]]s of sets of natural numbers.  The equivalence relation $A \equiv_{\mathrm{T}} B$ if $A \le_{\mathrm{T}} B$ and $B \le_{\mathrm{T}} A$ is ''Turing equivalence'' and the equivalence classes are the ''[[Turing degree]]s''.  Turing reducibility defines an partial order on the Turing degrees.

====References====
* Nies, André ''Computability and randomness'' Oxford Logic Guides '''51''' Oxford University Press (2009)  ISBN 0-19-923076-1 {{ZBL|1169.03034}}
* Pippenger, Nicholas  ''Theories of Computability''	Cambridge University Press (1997) ISBN 0-521-55380-6 {{ZBL|1200.03025}}