Content deleted Content added
m →Reductions weaker than Turing reducibility: typo in L(A) |
m →Turing reducibility: wikilink |
||
Line 18:
{{main|Turing reduction}}
The most fundamental reducibility notion is [[Turing reducibility]]. A set ''A'' of natural numbers is '''Turing reducible''' to a set ''B'' if and only if there is an [[oracle Turing machine]] that, when run with ''B'' as its oracle set, will compute the [[indicator function]] (characteristic function) of ''A''. Equivalently, ''A'' is Turing reducible to ''B'' if and only if there is an algorithm for computing the indicator function for ''A'' provided that the algorithm is provided with a means to correctly answer questions of the form "Is ''n'' in ''B''?".
Turing reducibility serves as a dividing line for other reducibility notions because, according to the [[Church-Turing thesis]], it is the most general reducibility relation that is effective. Reducibility relations that imply Turing reducibility have come to be known as '''strong reducibilities''', while those that are implied by Turing reducibility are '''weak reducibilities.''' Equivalently, a strong reducibility relation is one whose degrees form a finer equivalence relation than the Turing degrees, while a weak reducibility relation is one whose degrees form a coarser equivalence relation than Turing equivalence.
== Reductions stronger than Turing reducibility ==
| |||