In
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ...
, a Turing reduction from a
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
to a decision problem
is an
oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a s ...
which decides problem
given an oracle for
(Rogers 1967, Soare 1987). It can be understood as an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
that could be used to solve
if it had available to it a
subroutine
In computer programming, a function or subroutine is a sequence of program instructions that performs a specific task, packaged as a unit. This unit can then be used in programs wherever that particular task should be performed.
Functions ma ...
for solving ''B''. The concept can be analogously applied to
function problem
In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the ou ...
s.
If a Turing reduction from
to
exists, then every
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
for
can be used to produce an algorithm for
, by inserting the algorithm for
at each place where the oracle machine computing
queries the oracle for
. 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
or the oracle machine computing
. 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
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical c ...
in 1939 in terms of
oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a s ...
s. Later in 1943 and 1952
Stephen Kleene
Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of ...
defined an equivalent concept in terms of
recursive functions. In 1944
Emil Post
Emil Leon Post (; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.
Life
Post was born in Augustów, Suwałki Gove ...
used the term "Turing reducibility" to refer to the concept.
Definition
Given two sets
of natural numbers, we say
is Turing reducible to
and write
:
if there is an
oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a s ...
that computes the
characteristic function In mathematics, the term "characteristic function" can refer to any of several distinct concepts:
* The indicator function of a subset, that is the function
::\mathbf_A\colon X \to \,
:which for a given subset ''A'' of ''X'', has value 1 at point ...
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
In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
*There is an algorithm such that the ...
and ''B''-computably enumerable.
We say
is Turing equivalent to
and write
if both
and
The
equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
es of Turing equivalent sets are called
Turing degree
In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.
Overview
The concept of Turing degree is fund ...
s. The Turing degree of a set
is written
.
Given a set
, a set
is called Turing hard for
if
for all
. If additionally
then
is called Turing complete for
.
Relation of Turing completeness to computational universality
Turing completeness, as just defined above, corresponds only partially to
Turing completeness
In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Tu ...
in the sense of computational universality. Specifically, a Turing machine is a
universal Turing machine
In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simu ...
if its
halting problem
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a ...
(i.e., the set of inputs for which it eventually halts) is
many-one complete. Thus, a necessary ''but insufficient'' condition for a machine to be computationally universal, is that the machine's halting problem be Turing-complete for the set
of recursively enumerable sets. Insufficient because it may still be the case that, the language accepted by the machine is not itself recursively enumerable.
Example
Let
denote the set of input values for which the Turing machine with index ''e'' halts. Then the sets
and
are Turing equivalent (here
denotes an effective pairing function). A reduction showing
can be constructed using the fact that
. Given a pair
, a new index
can be constructed using the
smn theorem such that the program coded by
ignores its input and merely simulates the computation of the machine with index ''e'' on input ''n''. In particular, the machine with index
either halts on every input or halts on no input. Thus
holds for all ''e'' and ''n''. Because the function ''i'' is computable, this shows
. 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
In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly ...
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
is transitive: if
and
then
. Moreover,
holds for every set ''A'', and thus the relation
is a
preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special c ...
(it is not a
partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
because
and
does not necessarily imply
).
* There are pairs of sets
such that ''A'' is not Turing reducible to ''B'' and ''B'' is not Turing reducible to ''A''. Thus
is not a
total order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexiv ...
.
* There are infinite decreasing sequences of sets under
. Thus this relation is not
well-founded
In mathematics, a binary relation ''R'' is called well-founded (or wellfounded) on a class ''X'' if every non-empty subset ''S'' ⊆ ''X'' has a minimal element with respect to ''R'', that is, an element ''m'' not related by ''s  ...
.
* 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
to a set
has to determine whether a single element is in
in only finitely many steps, it can only make finitely many queries of membership in the set
. When the amount of information about the set
used to compute a single bit of
is discussed, this is made precise by the use function. Formally, the ''use'' of a reduction is the function that sends each natural number
to the largest natural number
whose membership in the set ''B'' was queried by the reduction while determining the membership of
in
.
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
is
many-one reducible to
if there is a
total computable function such that an element
is in
if and only if
is in
. Such a function can be used to generate a Turing reduction (by computing
, querying the oracle, and then interpreting the result).
* A
truth table reduction 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 ...
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) which, 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
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
of the reduction are important when studying subrecursive classes such as
P. A set ''A'' is
polynomial-time reducible to a set
if there is a Turing reduction of
to
that runs in polynomial time. The concept of
log-space reduction
In computational complexity theory, a log-space reduction is a reduction computable by a deterministic Turing machine using logarithmic space. Conceptually, this means it can keep a constant number of pointers into the input, along with a logari ...
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
In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a thesis about the nature of co ...
, a Turing reduction is the most general form of an effectively calculable reduction. Nevertheless, weaker reductions are also considered. Set
is said to be
arithmetical in
if
is definable by a formula of
Peano arithmetic
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...
with
as a parameter. The set
is
hyperarithmetical in
if there is a
recursive ordinal In mathematics, specifically computability and set theory, an ordinal \alpha is said to be computable or recursive if there is a computable well-ordering of a subset of the natural numbers having the order type \alpha.
It is easy to check that \ ...
such that
is computable from
, the α-iterated Turing jump of
. The notion of
relative constructibility is an important reducibility notion in set theory.
See also
*
Karp reduction
Notes
References
* M. Davis, ed., 1965. ''The Undecidable—Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions'', Raven, New York. Reprint, Dover, 2004. .
* 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.
*
* 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.
*
External links
NIST Dictionary of Algorithms and Data Structures: Turing reductionUniversity of Cambridge, Andrew Pitts, Tobias Kohn: Computation Theory
{{Authority control
Reduction (complexity)
Alan Turing
he:רדוקציה חישובית