# Turing reduction

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Turing_reduction
> Markdown URL: https://mediated.wiki/source/Turing_reduction.md
> Source: https://en.wikipedia.org/wiki/Turing_reduction
> Source revision: 1354639321
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Concept in computability theory}}

In [computability theory](/source/computability_theory), a '''Turing reduction''' from a [decision problem](/source/decision_problem) <math>A</math> to a decision problem <math>B</math> is an [oracle machine](/source/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](/source/algorithm) that could be used to solve <math>A</math> if it had access to a [subroutine](/source/subroutine) for solving <math>B</math>. The concept can be analogously applied to [function problem](/source/function_problem)s.

If a Turing reduction from <math>A</math> to <math>B</math> exists, then every [algorithm](/source/algorithm) for <math>B</math>{{efn|It is possible that ''B'' is an [undecidable problem](/source/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](/source/polynomial_time) is known as a '''[Cook reduction](/source/polynomial-time_reduction)'''.

The first formal definition of relative computability, then called relative reducibility, was given by [Alan Turing](/source/Alan_Turing) in 1939 in terms of [oracle machine](/source/oracle_machine)s. Later in 1943 and 1952 [Stephen Kleene](/source/Stephen_Kleene) defined an equivalent concept in terms of [recursive function](/source/Mu-recursive_function)s. In 1944 [Emil Post](/source/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](/source/if_and_only_if) there is an [oracle machine](/source/oracle_machine) that computes the [characteristic function](/source/Indicator_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](/source/partial_function) with domain ''A'', then ''A'' is said to be '''''B''-[recursively enumerable](/source/recursively_enumerable_set)''' 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](/source/equivalence_class)es of Turing equivalent sets are called '''[Turing degree](/source/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](/source/Turing_completeness) in the sense of computational universality.  Specifically, a Turing machine is a [universal Turing machine](/source/universal_Turing_machine) if its [halting problem](/source/halting_problem) (i.e., the set of inputs for which it eventually halts) is [many-one complete](/source/Many-one_reduction) 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](/source/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 [''{{subsup|S|n|m}}'' theorem](/source/Smn_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](/source/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](/source/preorder) (it is not a [partial order](/source/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](/source/total_order).
* There are infinite decreasing sequences of sets under <math>\leq_T</math>. Thus this relation is not [well-founded](/source/well-founded).
* Every set is Turing reducible to its own [Turing jump](/source/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 reducible](/source/many-one_reduction)''' to <math>B</math> if there is a [total computable function](/source/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](/source/truth-table_reduction)''' or a '''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](/source/Computational_complexity_theory) of the reduction are important when studying subrecursive classes such as [P](/source/P_(complexity)).  A set ''A'' is '''[polynomial-time reducible](/source/Polynomial-time_reduction)''' 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](/source/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](/source/Church%E2%80%93Turing_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](/source/arithmetical_set) in''' <math>B</math> if <math>A</math> is definable by a formula of [Peano arithmetic](/source/Peano_arithmetic) with <math>B</math> as a parameter.  The set <math>A</math> is '''[hyperarithmetical](/source/hyperarithmetical_hierarchy) in''' <math>B</math>  if there is a [recursive ordinal](/source/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 '''[relative constructibility](/source/Constructible_universe)''' is an important reducibility notion in [set theory](/source/set_theory).

== See also ==
* [Karp reduction](/source/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](/source/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](/source/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](/source/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](/source/Proceedings_of_the_London_Mathematical_Society)'', ser. 2 v. 45, pp.&nbsp;161–228. Reprinted in "The Undecidable", M. Davis ed., 1965.
* [H. Rogers](/source/Hartley_Rogers), 1967. Theory of recursive functions and effective computability. McGraw-Hill.
* [R. Soare](/source/Robert_I._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](/source/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:רדוקציה חישובית](/source/he%3A%D7%A8%D7%93%D7%95%D7%A7%D7%A6%D7%99%D7%94_%D7%97%D7%99%D7%A9%D7%95%D7%91%D7%99%D7%AA)

---
Adapted from the Wikipedia article [Turing reduction](https://en.wikipedia.org/wiki/Turing_reduction) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Turing_reduction?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.