A Theory of Oracle Machines: (Preliminary version)
Jonathan F. Buss · 1987
A theory of general oracle machines is presented which focuses on the power of a machine to access the oracle set. Turing machines with advice are a special case of oracle machines in this theory. Under appropriate definitions, simulations involving time and space bounded deterministic, nondeterministic and alternation Turing machines, auxiliary pushdown automata, stack automata, and nonerasing stack automata hold relative to any oracle. It is argued that these relativisation results are manifestations of a simple property shared by all of the simulations.