Difference between revisions of "Turing reducibility"
(Start article: Turing reduciblity) |
m (→References: isbn link) |
||
| (2 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | 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. | + | 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==== | ====References==== | ||
| − | * Nies, André ''Computability and randomness'' Oxford Logic Guides '''51''' Oxford University Press (2009) ISBN 0-19-923076-1 {{ZBL|1169.03034}} | + | * Nies, André ''Computability and randomness'' Oxford Logic Guides '''51''' Oxford University Press (2009) {{ISBN|0-19-923076-1}} {{ZBL|1169.03034}} |
| − | * Pippenger, Nicholas | + | * Pippenger, Nicholas ''Theories of Computability'' Cambridge University Press (1997) {{ISBN|0-521-55380-6}} {{ZBL|1200.03025}} |
Latest revision as of 19:32, 17 November 2023
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
Turing reducibility. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Turing_reducibility&oldid=37578