Meaning of oracle machine | Babel Free

Definitions

In computability theory, a form of theoretical Turing machine, able to solve even undecidable decision problems in a single operation.

Examples

“See also: o-machine”

“Thus, an oracle machine (which enacts an oracle algorithm) would be like an ordinary Turing machine, except that adjoined to its ordinary computational operations would be another operation: ‘Call in the oracle and ask it whether C_q(n) stops; […]”

CEFR level