In computability theory, a **Turing reduction** from a problem *A* to a problem *B*, is a reduction which solves *A*, assuming *B* is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve *A* if it had available to it a subroutine for solving *B*. 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.

A polynomial-time Turing reduction is known as a **Cook reduction**, after Stephen Cook.

Read more about Turing Reduction: Definition, Example, Properties, The Use of A Reduction, Stronger Reductions, Weaker Reductions

### Other articles related to "turing reduction, turing, reduction, reductions":

**Turing Reduction**- 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 ... in B if there is a recursive ordinal α such that A is computable from, the α-iterated

**Turing**jump of B ...

... In computability theory, a truth-table

**reduction**is a

**reduction**from one set of natural numbers to another ... As a "tool", it is weaker than

**Turing reduction**, since not every

**Turing reduction**between sets can be performed by a truth-table

**reduction**, but every truth-table ... For the same reason it is said to be a stronger reducibility than

**Turing**reducibility, because it implies

**Turing**reducibility ...

### Famous quotes containing the word reduction:

“The *reduction* of nuclear arsenals and the removal of the threat of worldwide nuclear destruction is a measure, in my judgment, of the power and strength of a great nation.”

—Jimmy Carter (James Earl Carter, Jr.)