Turing reduction

From Wikipedia, the free encyclopedia

In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which easily solves A, assuming B is easy to solve (Rogers 1967, Soare 1987). More formally, a Turing reduction is a function computable by an oracle machine with an oracle for B. Turing reductions can be applied to both decision problems and function problems.

If a Turing reduction of 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 M or the oracle machine, and may require as much space as both together.

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.

1 Definition
2 Example
3 Properties
4 Weaker reductions
5 Stronger reductions
6 References
7 External links

[edit] Definition

Given two sets $A,B \subseteq \mathbb{N}$ we say $A$ is Turing reducible to $B$ and write

$A \leq_T B$

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 $A$ is Turing equivalent to $B$ and write $A \equiv_T B\,$ if both $A \leq_T B$ and $B \leq_T A.$ The equivalence classes of Turing equivalent sets are called Turing degrees. The Turing degree of a set $X$ is written $\textbf{deg}(X)$ .

Given a set $\mathcal{X} \subseteq \mathcal{P}(\mathbb{N})$ , a set $A \subseteq \mathbb{N}$ is called Turing hard for $\mathcal{X}$ if $X \leq_T A$ for all $X \in \mathcal{X}$ . If additionally $A \in \mathcal{X}$ then $A$ is called Turing complete for $\mathcal{X}$ .

[edit] Example

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 $(e, n)$ 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 s-m-n 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.

[edit] Properties

Every set is Turing equivalent to its complement
Every computable set is Turing reducible to every other computable set. Because these sets can be computed with no oracle, they can be computed by an oracle machine that ignores the oracle it is given.
The relation $\leq_T$ is transitive: if $A \leq_T B$ and $B \leq_T C$ then $A \leq_T C$ . Moreover $A \leq A$ holds for every set A, and thus the relation $\leq_T$ is a partial order.
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 linear order.
There are infinite descreasing 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.

[edit] Weaker reductions

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

A set A is many-one reducible to B if there is a computable function f such that an element n is in A if and only if f(n) is in B. Such a function can be used to generate a Turing reduction (by computing f(n), querying the oracle, and then interpreting the result).
A truth table reduction must present all of its oracle queries at the same time, together with a boolean function (a truth table) which, when given the answers to the queries, will produce the final answer of the reduction.

The second way to produce a weaker 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 B if there is a Turing reduction of A to B that runs in polynomial time. The concept of log-space reduction is similar.

[edit] Stronger reductions

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

[edit] References

M. Davis, ed., 1965. The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven, New York. Reprint, Dover, 2004. ISBN 0-486-43228-9.
S. C. Kleene, 1952. Introduction to Metamathematics. Amsterdam: North-Holland.
S. C. Kleene and E. L. Post, 1954. "The upper semi-lattice of degrees of recursive unsolvability". Annals of Mathematics v. 2 n. 59, 379--407.
E. Post, 1944. "Recursively enumerable sets of positive integers and their decision problems." Bulletin of the American Mathematical Society, v. 50, pp. 284-316. Reprinted in "The Undecidable", M. Davis ed., 1965.
A. Turing, 1939. "Systems of logic based on ordinals." Proceedings of the London Mathematics Society, ser. 2 v. 45, pp. 161–228. Reprinted in "The Undecidable", M. Davis ed., 1965.
H. Rogers, 1967. Theory of recursive functions and effective computability. McGraw-Hill.
R. Soare, 1987. Recursively enumerable sets and degrees, Springer.