In computability theory, a Turing reduction from a decision problem
is an oracle machine that decides problem
(Rogers 1967, Soare 1987) in finitely many steps.
The concept can be analogously applied to function problems.
at each place where the oracle machine computing
However, because the oracle machine may query the oracle a large number of times, the resulting algorithm may require more time asymptotically than either the algorithm for
The first formal definition of relative computability, then called relative reducibility, was given by Alan Turing in 1939 in terms of oracle machines.
Later in 1943 and 1952 Stephen Kleene defined an equivalent concept in terms of recursive functions.
In 1944 Emil Post used the term "Turing reducibility" to refer to the concept.
If there is an oracle machine that, when run with oracle B, computes a partial function with domain A, then A is said to be B-recursively enumerable and B-computably enumerable.
Turing completeness, as just defined above, corresponds only partially to Turing completeness in the sense of computational universality.
Specifically, a Turing machine is a universal Turing machine if its halting problem (i.e., the set of inputs for which it eventually halts) is many-one complete for the set
Thus, a necessary but insufficient condition for a machine to be computationally universal, is that the machine's halting problem be Turing-complete for
Insufficient because it may still be the case that, the language accepted by the machine is not itself recursively enumerable.
denote the set of input values for which the Turing machine with index e halts.
denotes an effective pairing function).
can be constructed using the smn theorem such that the program coded by
ignores its input and merely simulates the computation of the machine with index e on input n. In particular, the machine with index
holds for all e and n. Because the function i is computable, this shows
is discussed, this is made precise by the use function.
Formally, the use of a reduction is the function that sends each natural number
was queried by the reduction while determining the membership of
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.
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
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.
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.
is definable by a formula of Peano arithmetic with