# 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 functions 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 degrees*. 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

**How to Cite This Entry:**

Turing reducibility.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Turing_reducibility&oldid=39339