Editing Turing reduction

{{Short description|Concept in computability theory}}
In [[computability theory]], a '''Turing reduction''' from a [[decision problem]] <math>A</math> to a decision problem <math>B</math> is an [[oracle machine]] that decides problem <math>A</math> given an oracle for <math>B</math> (Rogers 1967, Soare 1987) in finitely many steps. It can be understood as an [[algorithm]] that could be used to solve <math>A</math> if it had access to a [[subroutine]] for solving <math>B</math>. The concept can be analogously applied to [[function problem]]s.

If a Turing reduction from <math>A</math> to <math>B</math> exists, then every [[algorithm]] for <math>B</math>{{efn|It is possible that ''B'' is an [[undecidable problem]] for which no algorithm exists.}} can be used to produce an algorithm for <math>A</math>, by inserting the algorithm for <math>B</math> at each place where the oracle machine computing <math>A</math> queries the oracle for <math>B</math>. 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 <math>B</math> or the oracle machine computing <math>A</math>. A Turing reduction in which the oracle machine runs in [[polynomial time]] is known as a '''[[polynomial-time reduction#Turing reductions|Cook reduction]]'''.

The first formal definition of relative computability, then called relative reducibility, was given by [[Alan Turing]] in 1939 in terms of [[oracle machine]]s. Later in 1943 and 1952 [[Stephen Kleene]] defined an equivalent concept in terms of [[Mu-recursive function|recursive function]]s. In 1944 [[Emil Post]] used the term "Turing reducibility" to refer to the concept.

== Definition ==

Given two sets <math>A,B \subseteq \mathbb{N}</math> of natural numbers, we say <math>A</math> is '''Turing reducible''' to <math>B</math> and write
:<math>A \leq_T B</math>
[[if and only if]] there is an [[oracle machine]] that computes the [[Indicator function|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 set|recursively enumerable]]''' and '''''B''-computably enumerable'''.

We say <math>A</math> is '''Turing equivalent''' to <math>B</math> and write <math>A \equiv_T B\,</math> if both <math>A \leq_T B</math>  and <math>B \leq_T A.</math> The [[equivalence class]]es of Turing equivalent sets are called '''[[Turing degree]]s'''. The Turing degree of a set <math>X</math> is written <math>\textbf{deg}(X)</math>.

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

===Relation of Turing completeness to computational universality===
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 reduction|many-one complete]] for the set <math>\mathcal{X}</math> 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 <math>\mathcal{X}</math>. Insufficient because it may still be the case that, the language accepted by the machine is not itself recursively enumerable.

== Example ==

Let <math>W_e</math> denote the set of input values for which the Turing machine with index ''e'' halts.  Then the sets <math>A = \{e \mid e \in W_e\}</math> and <math>B = \{(e,n) \mid n \in W_e \}</math> are Turing equivalent (here <math>(-,-)</math> denotes an effective [[pairing function]]).  A reduction showing <math>A \leq_T B</math> can be constructed using the fact that <math>e \in A \Leftrightarrow (e,e) \in B</math>.  Given a pair <math>(e,n)</math>, a new index <math>i(e,n)</math> can be constructed using the [[Smn theorem|s<sub>mn</sub> theorem]] such that the program coded by <math>i(e,n)</math> ignores its input and merely simulates the computation of the machine with index ''e'' on input ''n''.  In particular, the machine with index <math>i(e,n)</math> either halts on every input or halts on no input.  Thus <math>i(e,n) \in A \Leftrightarrow (e,n) \in B</math> holds for all ''e'' and ''n''.  Because the function ''i'' is computable, this shows <math>B \leq_T A</math>.  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 <math>\leq_T</math> is transitive: if <math>A \leq_T B</math> and <math>B \leq_T C</math> then <math>A \leq_T C</math>.  Moreover, <math>A \leq_T A</math> holds for every set ''A'', and thus the relation <math>\leq_T</math> is a [[preorder]] (it is not a [[partial order]] because <math>A \leq_T B</math> and <math>B \leq_T A </math> does not necessarily imply <math>A = B</math>).
* There are pairs of sets <math>(A,B)</math>  such that ''A'' is not Turing reducible to ''B'' and ''B'' is not Turing reducible to ''A''.  Thus <math>\leq_T</math> is not a [[total order]].
* There are infinite decreasing sequences of sets under <math>\leq_T</math>. 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 <math>A</math> to a set <math>B</math> has to determine whether a single element is in <math>A</math> in only finitely many steps, it can only make finitely many queries of membership in the set <math>B</math>. When the amount of information about the set <math>B</math> used to compute a single bit of <math>A</math> is discussed, this is made precise by the ''use'' function. Formally, the ''use'' of a reduction is the function that sends each natural number <math>n</math> to the largest natural number <math>m</math> whose membership in the set <math>B</math> was queried by the reduction while determining the membership of <math>n</math> in <math>A</math>.

== 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 <math>A</math> is '''[[many-one reduction|many-one reducible]]''' to <math>B</math> if there is a [[Computable function|total computable function]] <math>f</math> such that an element <math>n</math> is in <math>A</math> if and only if <math>f(n)</math> is in <math>B</math>.  Such a function can be used to generate a Turing reduction (by computing <math>f(n)</math>, querying the oracle, and then interpreting the result).
* A '''[[truth table reduction]]''' or a '''[[truth table reduction|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 theory|computational complexity]] of the reduction are important when studying subrecursive classes such as [[P (complexity)|P]].  A set ''A'' is '''[[Polynomial-time reduction|polynomial-time reducible]]''' to a set <math>B</math> if there is a Turing reduction of <math>A</math> to <math>B</math> 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 <math>A</math> is said to be '''[[arithmetical set|arithmetical]] in''' <math>B</math> if <math>A</math> is definable by a formula of [[Peano arithmetic]] with <math>B</math> as a parameter.  The set <math>A</math> is '''[[hyperarithmetical hierarchy|hyperarithmetical]] in''' <math>B</math>  if there is a [[recursive ordinal]] <math>\alpha</math> such that <math>A</math> is computable from <math>B^{(\alpha)}</math>, the ''α''-iterated Turing jump of <math>B</math>.  The notion of '''[[Constructible universe#Relative constructibility|relative constructibility]]''' is an important reducibility notion in [[set theory]].

== See also ==
* [[Karp reduction]]

== Notes ==
{{notelist}}

== References ==

* M. Davis, ed., 1965.  ''The Undecidable&mdash;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.
* {{ cite journal
   | last = Post
   | first = E. L.
   | author-link = Emil Leon Post
   | title = Recursively enumerable sets of positive integers and their decision problems
   | journal = [[Bulletin of the American Mathematical Society]]
   | volume = 50
   | year = 1944
   | issue = 5
 | pages = 284–316
   | url = http://projecteuclid.org/download/pdf_1/euclid.bams/1183505800
   | format = [[PDF]]
   | accessdate = 2015-12-17
   | doi=10.1090/s0002-9904-1944-08111-1| doi-access = free
   }}
* A. Turing, 1939. "Systems of logic based on ordinals." ''[[Proceedings of the London Mathematical Society]]'', ser. 2 v. 45, pp.&nbsp;161–228. Reprinted in "The Undecidable", M. Davis ed., 1965.
* [[Hartley Rogers|H. Rogers]], 1967. Theory of recursive functions and effective computability. McGraw-Hill.
* [[Robert I. Soare|R. Soare]], 1987. Recursively enumerable sets and degrees, Springer.
* {{ cite journal
   | last = Davis
   | first = Martin
   | author-link = Martin Davis (mathematician)
   | title = What is...Turing Reducibility?
   | journal = [[Notices of the American Mathematical Society]]
   |date=November 2006
   | volume = 53
   | issue = 10
   | pages =1218–1219
   | url = http://www.ams.org/notices/200610/whatis-davis.pdf
   | accessdate = 2008-01-16 }}

== External links ==
* [https://xlinux.nist.gov/dads/HTML/turingredctn.html NIST Dictionary of Algorithms and Data Structures: Turing reduction]
*[https://www.cl.cam.ac.uk/teaching/2122/CompTheory/comt-notes.pdf University of Cambridge, Andrew Pitts, Tobias Kohn: Computation Theory]
*[https://www.cis.upenn.edu/~jean/home.html Prof. Jean Gallier’s Homepage]
{{Alan Turing|state=expanded}}
{{Authority control}}

[[Category:Reduction (complexity)]]
[[Category:Alan Turing]]

[[he:רדוקציה חישובית]]