go-v.orgcodex
Menu
Page tools

codex · Philosophy

Oracle machine

In complexity theory and computability theory, an oracle machine is an abstract machine that can query a black box called an oracle, which is able to give an answer to any instance of a certain problem ⁠R⁠ in a single operation. The problem ⁠R⁠ can be of any complexity class, or it can even be an undecidable problem such as the halting problem. If another problem ⁠R′⁠ is reducible to ⁠R⁠ in polynomial time, then the oracle machine (with the ⁠R⁠-oracle) can solve ⁠R′⁠ in polynomial time; one can say that ⁠R′⁠ is in the relativized complexity class ⁠𝖯R⁠. Other relativized complexity classes such as ⁠𝖭𝖯R⁠ can be defined analogously.

Wikipedia contributors, "Oracle machine", Wikipedia, revision 1367962950, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex