Oracle machine

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 oracle, which is able to decide certain decision problems in a single step. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used.

Related Topics:
Complexity theory - Computability theory - Abstract machine - Decision problem - Turing machine - Complexity class - Undecidable - Halting problem

~ ~ ~ ~ ~ ~ ~ ~ ~ ~