A Boolean oracle is a function \(O : \{ 0,1\} ^* \to \{ 0,1\} \); it decides a language \(A\) if \(O(w) = 1 \iff w \in A\) for every \(w\). An oracle TM with \(k\) work tapes has a finite state type with decidable equality, a start state and a halt state; the input, \(k\) work and output tapes of an ordinary TM plus a dedicated read-write query tape; a partial map sending each query state to a pair (yes-successor, no-successor); and a local transition that reads the symbols under all heads (the query head included), writes symbols of \(\Gamma _w\) on the query, work and output tapes, and moves every head, moving right every head that reads \(\triangleright \). The initial configuration on \(x\) is in the start state with \(x\) on the input tape and every other tape empty. One step relative to \(O\) is defined as follows. The halt state has no successor. In a non-halted query state the machine reads the query word, formed by the cells strictly between the left marker and the query head in left-to-right order (a cell reads \(1\) only if it holds \(1\); \(0\), blank and \(\triangleright \) read as \(0\)), and enters the yes-successor if \(O\) answers \(1\) on it and the no-successor otherwise. The lookup costs exactly one step and changes nothing but the state; in particular the query tape is not erased, and writing the query costs ordinary local steps. Every other non-halted state applies the local transition. The relation \(c \to _O^t c'\) holds when \(c'\) is reached from \(c\) in exactly \(t\) steps relative to \(O\).

Fix an oracle \(O\) and an oracle TM \(M\); all runs are relative to \(O\), and every step, local or lookup, counts toward a budget. \(M\) accepts \(x\) (within \(t\) steps) if the run on \(x\) reaches the halt state (after at most \(t\) steps) with output cell \(1\) equal to \(1\). \(M\) decides \(L\) in time \(T : \mathbb {N} \to \mathbb {N}\) if on every input \(x\) it reaches the halt state within \(T(|x|)\) steps, with output cell \(1\) equal to \(1\) if \(x \in L\) and equal to \(0\) if \(x \notin L\). \(M\) halts on a program \(p\) within \(t\) steps if the run on \(p\) reaches the halt state after at most \(t\) steps, and produces \(y\) on \(p\) within \(t\) steps if moreover the halted output tape has output \(y\). \(M\) halts on \(p\) (produces \(y\) on \(p\)) if it does so within some finite budget. These have the same shape as the corresponding definitions for ordinary machines.

Every TM with \(k\) work tapes is an oracle TM with \(k\) work tapes, the same states, start and halt state, and no query states. Its local transition applies the source transition to the input, work and output tapes and keeps the query tape inert: it writes only blanks there, and moves the query head right when it reads \(\triangleright \) and leaves it in place otherwise. Erasing the query tape maps an oracle configuration to the ordinary configuration with the same state and input, work and output tapes.

An oracle machine \(U\) simulates an oracle machine \(M\) under a compiler \(c : \{ 0,1\} ^* \to \{ 0,1\} ^*\) if for every oracle \(O\) and program \(p\): \(U\) halts on \(c(p)\) relative to \(O\) if and only if \(M\) halts on \(p\) relative to \(O\), and for every \(y\), \(U\) produces \(y\) on \(c(p)\) relative to \(O\) if and only if \(M\) produces \(y\) on \(p\) relative to \(O\). \(U\) simulates \(M\) under \(c\) in time \(\tau : \{ 0,1\} ^* \times \mathbb {N} \to \mathbb {N}\) if for every oracle \(O\), whenever \(M\) produces \(y\) on \(p\) within \(t\) steps relative to \(O\), \(U\) produces \(y\) on \(c(p)\) within \(\tau (p, t)\) steps relative to \(O\); unlike the ordinary timed simulation, bounded halting alone is not required to transfer. \(U\) is universal if for every \(k\) and every oracle machine \(M\) with \(k\) work tapes there is a compiler \(c\), computable by an ordinary deterministic machine, such that \(U\) simulates \(M\) under \(c\). For a policy of admissible clocks, \(U\) is efficiently universal for the policy if moreover \(c\) has additive overhead (\(|c(p)| \le |p| + C\)) and \(U\) simulates \(M\) under \(c\) in some admissible clock \(\tau \); it is efficiently universal if this holds for the polynomial policy, which admits \(\tau \) when \(\tau (p, t) \le a (|p| + t + 1)^e\) for some constants \(a, e\). In every case the compiler, constant and clock depend on \(M\) but are chosen once for all oracles.

An oracle NTM has two local transition functions selected by a choice bit and the same query mechanism and cost as an oracle TM, with execution along a fixed choice sequence and existential acceptance within a time bound.

For a language \(A\), \(\mathsf{P}^A\) is the class of languages decided in polynomial time by an oracle TM relative to an oracle deciding \(A\), and \(\mathsf{NP}^A\) is the nondeterministic analogue. Query length is charged through the time needed to write the query.

An enumeration \(i \mapsto (M_i, p_i)\) of oracle TMs paired with polynomial clocks such that every polynomial-time oracle language, relative to every oracle, is decided by some clocked \(M_i\), and the clocked machines are simulated uniformly in the oracle.

For a set \(P\) of Boolean functions on \(n\) bits (necessarily finite), its density is the exact rational \(|P| / 2^{2^n}\), the fraction of all Boolean functions on \(n\) bits that lie in \(P\).

\(f : \mathbb {N} \to \mathbb {R}\) is negligible if for every \(c \in \mathbb {N}\) there is \(N {\gt} 0\) with \(|f(n)| {\lt} 1 / n^c\) for all \(n \ge N\).

A family of properties \(P_n\) of \(n\)-bit Boolean functions is large with density \(\delta (n)\) if \(\mathrm{density}(P_n) \ge \delta (n)\); constructive if membership of a truth table of length \(N = 2^n\) is decidable in time polynomial in \(N\) (or by circuits of size polynomial in \(N\)); and useful against \(\mathsf{SIZE}(s)\) if, for all sufficiently large \(n\), no function in \(P_n\) has circuits of size \(s(n)\). The quantifier over lengths and the scale of constructivity are part of the definition.

A keyed family \(f_k : \{ 0,1\} ^n \to \{ 0,1\} \) computable in polynomial time, and its security game against a nonuniform class of distinguishers with oracle access (or with the full truth table): the advantage in telling \(f_k\) for a random key from a uniformly random function, required to be negligible, or bounded by an explicit function of the distinguisher’s size.