↑ arvau

Wikipedia / Turing reduction

In computability theory, a Turing reduction from a decision problem is an oracle machine (Rogers 1967, Soare 1987) in finitely many steps. It can be understood as an algorithm if it had access to a subroutine. The concept can be analogously applied to function problems.

exists, then every algorithm. 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 functionss. In 1944 Emil Post used the term "Turing reducibility" to refer to the concept.

Definition

is Turing reducible and write

if and only if there is an oracle machine that computes the 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 and B-computably enumerable.

is Turing equivalent The equivalence classes of Turing equivalent sets are called Turing degrees.

is called Turing hard is called Turing complete.

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 complete of recursively enumerable sets. Thus, a necessary but insufficient. Insufficient because it may still be the case that, the language accepted by the machine is not itself recursively enumerable.

Example

denote the set of input values for which the Turing machine with index e denotes an effective pairing function can be constructed using the Snm theorem ignores its input and merely simulates the computation of the machine with index e on input n holds for all e and n. Because the function i. 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.

  • holds for every set A is a preorder (it is not a partial order).

  • such that A is not Turing reducible to B and B is not Turing reducible to A is not a total order.

  • . 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

is discussed, this is made precise by the use function. Formally, the use.

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.

  • is many-one reducible if there is a total computable function, querying the oracle, and then interpreting the result).

  • 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) 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 of the reduction are important when studying subrecursive classes such as P. A set A is polynomial-time reducible 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 is said to be arithmetical in is definable by a formula of Peano arithmetic is hyperarithmetical in if there is a recursive ordinal, the α. The notion of relative constructibility is an important reducibility notion in set theory.

See also

Notes

References

  • M. Davis, ed., 1965. The UndecidableBasic 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 Mathematical 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.

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