Loading AI tools
Concept in computability theory From Wikipedia, the free encyclopedia
In computability theory, a Turing reduction from a decision problem to a decision problem is an oracle machine that decides problem given an oracle for (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve if it had available to it a subroutine for solving . The concept can be analogously applied to function problems.
If a Turing reduction from to exists, then every algorithm for [lower-alpha 1] can be used to produce an algorithm for , by inserting the algorithm for at each place where the oracle machine computing queries the oracle for . 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 or the oracle machine computing . A Turing reduction in which the oracle machine runs in polynomial time is known as a Cook reduction.
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.
Given two sets of natural numbers, we say is Turing reducible to and write
if and only if there is an oracle machine that computes the characteristic function of A when run with oracle B. In this case, we also say A is B-recursive and B-computable.
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.
We say is Turing equivalent to and write if both and The equivalence classes of Turing equivalent sets are called Turing degrees. The Turing degree of a set is written .
Given a set , a set is called Turing hard for if for all . If additionally then is called Turing complete for .
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 of recursively enumerable sets. 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.
Let denote the set of input values for which the Turing machine with index e halts. Then the sets and are Turing equivalent (here denotes an effective pairing function). A reduction showing can be constructed using the fact that . Given a pair , a new index 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 either halts on every input or halts on no input. Thus holds for all e and n. Because the function i is computable, this shows . The reductions presented here are not only Turing reductions but many-one reductions, discussed below.
Since every reduction from a set to a set has to determine whether a single element is in in only finitely many steps, it can only make finitely many queries of membership in the set . When the amount of information about the set used to compute a single bit of is discussed, this is made precise by the use function. Formally, the use of a reduction is the function that sends each natural number to the largest natural number whose membership in the set was queried by the reduction while determining the membership of in .
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 if there is a Turing reduction of to 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.
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 is said to be arithmetical in if is definable by a formula of Peano arithmetic with as a parameter. The set is hyperarithmetical in if there is a recursive ordinal such that is computable from , the α-iterated Turing jump of . The notion of relative constructibility is an important reducibility notion in set theory.