Turing reduction

Concept in computability theory

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.

From Wikipedia, under CC BY-SA. More on occurri.