Definitions for oracle machine
This page provides all possible meanings and translations of the word oracle machine
In computability theory, a form of theoretical Turing machine, able to decide certain decision problems in a single operation.
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 decide certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used.
Find a translation for the oracle machine definition in other languages:
Select another language:
Discuss these oracle machine definitions with the community:
Use the citation below to add this definition to your bibliography:
"oracle machine." Definitions.net. STANDS4 LLC, 2014. Web. 20 Apr. 2014. <http://www.definitions.net/definition/oracle machine>.