Concept in computability theory
5 statements · 20% with external sources · numbers in brackets are citations
4 identifiers linking Turing reduction across the web's reference databases
From Wikipedia, the free encyclopedia · Read full article · Text CC BY-SA 4.0
In computability theory, a Turing reduction from a decision problem to a decision problem is an oracle machine that decides problem given an oracle for in finitely many steps. It can be understood as an algorithm that could be used to solve if it had access to a subroutine for solving . The concept can be analogously applied to function problems.