Concept

Turing reduction

Overview

In computability theory, a Turing reduction from a decision problem

A

{\displaystyle A}

to a decision problem

B

{\displaystyle B}

is an oracle machine that decides problem

A

{\displaystyle A}

given an oracle for

B

{\displaystyle B}

(Rogers 1967, Soare 1987) in finitely many steps. It can be understood as an algorithm that could be used to solve

A

{\displaystyle A}

if it had access to a subroutine for solving

B

{\displaystyle B}

. The concept can be analogously applied to function problems.

If a Turing reduction from

A

{\displaystyle A}

to

B

{\displaystyle B}

exists, then every algorithm for

B

{\displaystyle B}

can be used to produce an algorithm for

A

{\displaystyle A}

, by inserting the algorithm for

B

{\displaystyle B}

at each place where the oracle machine computing

A

{\displaystyle A}

queries the oracle for

B

{\displaystyle 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

{\displaystyle B}

or the oracle machine computing

A

{\displaystyle 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.

Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).

Possible passages

Found by search and not yet checked by a person; they may only mention the idea in passing.

1. Thus there arises a classification of modes of formation, or in the language commonly used by mathematicians, a classification of Functions. Any number, considered as formed from any other number, is called a function of it; and there are as many kinds of functions as there are modes of formation. The simple functions are by no means numerous, most functions being formed by the combination of several of the…

   John Stuart Mill, A System of Logic, Ratiocinative and Inductive

   States what Turing reduction is.

   Read the chapter · Open in the reader

2. However, even a cursory examination of a modern treatise on geometry makes clear what has taken place. For example, Professor Hilbert begins his _Grundlagen der Geometrie_, not with definition of points, lines, and planes, but with the assumption of three different systems of things (Dinge) of which the first, called…

   John Dewey, Creative Intelligence

   States what Turing reduction is.

   Read the chapter · Open in the reader

3. This is nothing else than the necessity of abstract logic, which is the presupposition involved in the very fact of interrelated existence as disclosed in each immediate occasion of experience. The key to the pattern means this fact:—that from a select set of those general conditions, exemplified in any one and the same occasion, a pattern involving an infinite variety of other such conditions, also exemplified in…

   Alfred North Whitehead, Science and the modern world

   States what Turing reduction is.

   Read the chapter · Open in the reader

Related ideas

• Alan Turing
• If and only if
• Computability theory
• Partially ordered set
• Peano axioms
• Set theory
• Total order
• Emil Leon Post
• Time complexity
• Church–Turing thesis
• Computational complexity theory
• Turing degree
• Algorithm
• Decision problem
• Constructible universe
• Polynomial-time reduction
• Pairing function

Place in the tradition

Part of Reductionism.

Explore Turing reduction in the interactive graph →