Definition
Oracle Turing Machine
Let
be a language (the oracle). An oracle Turing machine for is a multitape Turing machine equipped with a distinguished query tape and three special states such that:
During a computation on input
, may enter . The string currently written on the query tape is interpreted as a query . In one abstract step, the machine is moved without changing any other tape contents (except possibly the head positions specified by the transition) to:
if
if
otherwise behaves like an ordinary Turing machine. We write
for with oracle . The language decided by is: Time measure: Unless stated otherwise, each oracle call counts as one unit of time. The running time of
on is the number of ordinary steps plus the number of oracle calls.