Turing reduction

Example

Let ${\displaystyle W_e}$ denote the set of input values for which the Turing machine with index e halts. Then the sets ${\displaystyle A=\{e\mid e\in W_e\}}$ and ${\displaystyle B=\{(e,n)\mid n\in W_e\}}$ are Turing equivalent (here ${\displaystyle (-,-)}$ denotes an effective pairing function). A reduction showing ${\displaystyle A{\le }_{T}B}$ can be constructed using the fact that ${\displaystyle e\in A\iff (e,e)\in B}$. Given a pair ${\displaystyle (e,n)}$, a new index ${\displaystyle i(e,n)}$ can be constructed using the S m
n theorem such that the program coded by ${\displaystyle i(e,n)}$ ignores its input and merely simulates the computation of the machine with index e on input n. In particular, the machine with index ${\displaystyle i(e,n)}$ either halts on every input or halts on no input. Thus ${\displaystyle i(e,n)\in A\iff (e,n)\in B}$ holds for all e and n. Because the function i is computable, this shows ${\displaystyle B{\le }_{T}A}$. The reductions presented here are not only Turing reductions but many-one reductions, discussed below.

Properties

• Every set is Turing equivalent to its complement.
• Every computable set is Turing reducible to every other set. Because any computable set can be computed with no oracle, it can be computed by an oracle machine that ignores the given oracle.
• The relation ${\displaystyle {\le }_T}$ is transitive: if ${\displaystyle A{\le }_{T}B}$ and ${\displaystyle B{\le }_{T}C}$ then ${\displaystyle A{\le }_{T}C}$. Moreover, ${\displaystyle A{\le }_{T}A}$ holds for every set A, and thus the relation ${\displaystyle {\le }_T}$ is a preorder (it is not a partial order because ${\displaystyle A{\le }_{T}B}$ and ${\displaystyle B{\le }_{T}A}$ does not necessarily imply ${\displaystyle A=B}$).
• There are pairs of sets ${\displaystyle (A,B)}$ such that A is not Turing reducible to B and B is not Turing reducible to A. Thus ${\displaystyle {\le }_T}$ is not a total order.
• There are infinite decreasing sequences of sets under ${\displaystyle {\le }_T}$. Thus this relation is not well-founded.
• Every set is Turing reducible to its own Turing jump, but the Turing jump of a set is never Turing reducible to the original set.

The use of a reduction

Since every reduction from a set ${\displaystyle A}$ to a set ${\displaystyle B}$ has to determine whether a single element is in ${\displaystyle A}$ in only finitely many steps, it can only make finitely many queries of membership in the set ${\displaystyle B}$. When the amount of information about the set ${\displaystyle B}$ used to compute a single bit of ${\displaystyle A}$ is discussed, this is made precise by the use function. Formally, the use of a reduction is the function that sends each natural number ${\displaystyle n}$ to the largest natural number ${\displaystyle m}$ whose membership in the set ${\displaystyle B}$ was queried by the reduction while determining the membership of ${\displaystyle n}$ in ${\displaystyle A}$.

Stronger reductions

There are two common ways of producing reductions stronger than Turing reducibility. The first way is to limit the number and manner of oracle queries.

• Set ${\displaystyle A}$ is many-one reducible to ${\displaystyle B}$ if there is a total computable function ${\displaystyle f}$ such that an element ${\displaystyle n}$ is in ${\displaystyle A}$ if and only if ${\displaystyle f(n)}$ is in ${\displaystyle B}$. Such a function can be used to generate a Turing reduction (by computing ${\displaystyle f(n)}$, querying the oracle, and then interpreting the result).
• A truth-table reduction or a weak truth-table reduction must present all of its oracle queries at the same time. In a truth table reduction, the reduction also gives a Boolean function (a truth table) that, when given the answers to the queries, will produce the final answer of the reduction. In a weak truth table reduction, the reduction uses the oracle answers as a basis for further computation depending on the given answers (but not using the oracle). Equivalently, a weak truth table reduction is one for which the use of the reduction is bounded by a computable function. For this reason, weak truth table reductions are sometimes called "bounded Turing" reductions.

The second way to produce a stronger reducibility notion is to limit the computational resources that the program implementing the Turing reduction may use. These limits on the computational complexity of the reduction are important when studying subrecursive classes such as P. A set A is polynomial-time reducible to a set ${\displaystyle B}$ if there is a Turing reduction of ${\displaystyle A}$ to ${\displaystyle B}$ that runs in polynomial time. The concept of log-space reduction is similar.

These reductions are stronger in the sense that they provide a finer distinction into equivalence classes, and satisfy more restrictive requirements than Turing reductions. Consequently, such reductions are harder to find. There may be no way to build a many-one reduction from one set to another even when a Turing reduction for the same sets exists.

Weaker reductions

According to the Church–Turing thesis, a Turing reduction is the most general form of an effectively calculable reduction. Nevertheless, weaker reductions are also considered. Set ${\displaystyle A}$ is said to be arithmetical in ${\displaystyle B}$ if ${\displaystyle A}$ is definable by a formula of Peano arithmetic with ${\displaystyle B}$ as a parameter. The set ${\displaystyle A}$ is hyperarithmetical in ${\displaystyle B}$ if there is a recursive ordinal ${\displaystyle \alpha }$ such that ${\displaystyle A}$ is computable from ${\displaystyle B^{(\alpha )}}$, the α-iterated Turing jump of ${\displaystyle B}$. The notion of relative constructibility is an important reducibility notion in set theory.