An oracle for a decision problem is an abstract device that returns its answer in a single computational step. An oracle Turing
machine has a special query tape and states that permit it to ask whether a finite
word belongs to a fixed formal
language 
. The languages decidable by such machines describe
computation relative to 
,
and the resulting reducibility is called Turing
reducibility.
Oracles need not be computable. They are used to compare the information content of problems and to define relativized complexity classes.
In numerical query complexity, a first-order oracle returns the value of a function and its gradient at a query point. The cost counts oracle queries, while other computation is not charged (Chewi et al. 2024).
A weak membership oracle for a convex body permits uncertainty within a prescribed tolerance of its boundary. This supplies an input model for geometric algorithms, including approximation of mixed volume (Chen and Liu 2026).
