Turing reduction

In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine that decides problem A given an oracle for B (Rogers 1967, Soare 1987) in finitely many steps. It can be understood as an algorithm that could be used to solve A if it had access to a subroutine for solving B . The concept can be analogously applied to function problems. If a Turing reduction from A to B exists, then every algorithm for B can be used to produce an algorithm for A , by inserting the algorithm for B at each place where the oracle machine computing A queries the oracle for B . 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 B or the oracle machine computing A . 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.

In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine that decides problem A given an oracle for B (Rogers 1967, Soare 1987) in finitely many steps. It can be understood as an algorithm that could be used to solve A if it had access to a subroutine for solving B . The concept can be analogously applied to function problems. If a Turing reduction from A to B exists, then every algorithm for B can be used to produce an algorithm for A , by inserting the algorithm for B at each place where the oracle machine computing A queries the oracle for B . 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 B or the oracle machine computing A . 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. Let W_e denote the set of input values for which the Turing machine with index e halts. Then the sets A = \{e \mid e \in W_e\} and B = \{(e,n) \mid n \in W_e \} are Turing equivalent (here (-,-) denotes an effective pairing function). A reduction showing A \leq_T B can be constructed using the fact that e \in A \Leftrightarrow (e,e) \in B . Given a pair (e,n) , a new index i(e,n) can be constructed using the theorem such that the program coded by 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 i(e,n) either halts on every input or halts on no input. Thus i(e,n) \in A \Leftrightarrow (e,n) \in B holds for all e and n. Because the function i is computable, this shows B \leq_T A . The reductions presented here are not only Turing reductions but many-one reductions, discussed below. The relation \leq_T is transitive: if A \leq_T B and B \leq_T C then A \leq_T C . Moreover, A \leq_T A holds for every set A, and thus the relation \leq_T is a preorder (it is not a partial order because A \leq_T B and B \leq_T A does not necessarily imply A = B ). There are pairs of sets (A,B) such that A is not Turing reducible to B and B is not Turing reducible to A. Thus \leq_T is not a total order. There are infinite decreasing sequences of sets under \leq_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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1362008460 under CC BY-SA 4.0; modifications have been made.