Reduction (recursion Theory) - Turing Reducibility

Turing Reducibility

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.