An oracle Turing machine with \(k\) ordinary work tapes over a symbol alphabet \(\Sigma \) and state set \(Q\) consists of an initial state \(q_0\), a designated query state \(q_{\mathrm{query}}\), a designated positive-answer state \(q_{\mathrm{yes}}\), a designated negative-answer state \(q_{\mathrm{no}}\), and a transition function that assigns to every state, scanned input symbol (possibly blank), and family of scanned symbols on the \(k+1\) work tapes (the last of which serves as the query tape) a one-step action on the \(k+1\) work tapes. The transition function governs every state except the query state, whose behavior is instead determined by the oracle. The structure itself does not require the three special states to be distinct; that is imposed separately by well-formedness.

An oracle Turing machine with \(k\) ordinary work tapes is well formed when its three special states are pairwise distinct: the query state differs from the positive-answer state, the query state differs from the negative-answer state, and the two answer states differ from each other. The initial state is allowed to coincide with the query state (such a machine submits the empty query on its first step).

For an oracle machine with \(k\) ordinary work tapes, the index of the query tape among the \(k+1\) work tapes: the last index, \(k\).

For a configuration of a machine with \(k+1\) work tapes over an alphabet \(\Sigma \), the query string is the word read off the query tape (the last work tape) from cell \(0\) rightward, up to but excluding the first blank cell. If no cell at a nonnegative position of the query tape is blank — possible for an arbitrary configuration, though not for one reachable from an initial configuration — the query string is defined to be the empty word.

One step of an oracle machine \(M\) with \(k\) ordinary work tapes relative to an oracle language \(O\) over the alphabet \(\Sigma \), acting on a configuration \(c\) with \(k+1\) work tapes. A halted configuration is left fixed. If the current state is the query state, the machine moves to the positive-answer state when the query string of \(c\) belongs to \(O\) and to the negative-answer state otherwise, with all tapes, head positions, and the output left unchanged. In every other state, the machine applies the action prescribed by its transition function for the current state and the scanned input and work-tape symbols, exactly like a plain multi-tape machine.

The initial configuration of an oracle machine with \(k\) ordinary work tapes on a given input word: the machine is in its initial state, the input head is at the origin, all \(k+1\) work tapes (including the query tape) are blank with their heads at the origin, and the output is empty.

The configuration reached by running an oracle machine \(M\) with oracle \(O\) for \(t\) steps from a configuration \(c\): the \(t\)-fold iterate of the one-step function of \(M\) relative to \(O\), applied to \(c\).

An oracle machine \(M\) with oracle \(O\) computes the word \(y\) on input \(x\) within \(t\) steps when, after running \(M\) relative to \(O\) for \(t\) steps from its initial configuration on \(x\), the machine has halted and its output tape holds exactly \(y\). This is a time-only notion; space is not constrained.

The extension of a one-step action on \(k\) work tapes to an action on \(k+1\) work tapes: on the first \(k\) tapes it writes and moves exactly as before, and on the extra last tape it writes nothing and does not move the head. The input-head move, the output emission, and the next state are unchanged.

The embedding of a configuration of a machine with \(k\) work tapes and state set \(Q\) into a configuration of a machine with \(k+1\) work tapes over the extended state set \(Q \sqcup \{ 0,1,2\} \): the state (if the machine has not halted) is renamed along the left inclusion, the input head, the first \(k\) work tapes with their head positions, and the output are unchanged, and the extra last work tape is blank with its head at the origin.

The embedding of a plain multi-tape machine with \(k\) work tapes and state set \(Q\) as an oracle machine over the extended state set \(Q \sqcup \{ 0,1,2\} \): the three fresh states serve as the query, positive-answer, and negative-answer states, the initial state is the image of the original initial state, and on original states the transition function is the original transition (renamed along the left inclusion and extended by an inert query tape), so that the machine never moves into a fresh state and ignores the query tape. From each of the three fresh states the transition table halts immediately.

Given an oracle machine \(M\) with \(k\) ordinary work tapes and state set \(Q\), the plain multi-tape machine with \(k+1\) work tapes over the same state set \(Q\) that simulates \(M\) run with the empty oracle: it has the same initial state, and its transition function agrees with that of \(M\) in every state except the query state, where it instead performs a stationary move (no writes, no head movement, no output) directly into the negative-answer state, since the empty oracle always answers no.