Editing Turing reduction (section)

{{Short description|Concept in computability theory}}
In [[computability theory]], a '''Turing reduction''' from a [[decision problem]] <math>A</math> to a decision problem <math>B</math> is an [[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]] that could be used to solve <math>A</math> if it had access to a [[subroutine]] for solving <math>B</math>. The concept can be analogously applied to [[function problem]]s.

If a Turing reduction from <math>A</math> to <math>B</math> exists, then every [[algorithm]] for <math>B</math>{{efn|It is possible that ''B'' is an [[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]] is known as a '''[[polynomial-time reduction#Turing reductions|Cook reduction]]'''.

The first formal definition of relative computability, then called relative reducibility, was given by [[Alan Turing]] in 1939 in terms of [[oracle machine]]s. Later in 1943 and 1952 [[Stephen Kleene]] defined an equivalent concept in terms of [[Mu-recursive function|recursive function]]s. In 1944 [[Emil Post]] used the term "Turing reducibility" to refer to the concept.