The read alphabet is \(\Gamma = \{ 0, 1, \sqcup , \triangleright \} \) and the write alphabet is \(\Gamma _w = \{ 0, 1, \sqcup \} \), so no transition can write the start symbol \(\triangleright \). A head moves left, right, or stays. A tape is a head position \(h \in \mathbb {N}\) together with contents \(\mathbb {N} \to \Gamma \); the type allows any symbol in any cell. Initial tapes have \(\triangleright \) in cell \(0\) and nowhere else, writing at cell \(0\) is a no-op, and moving left at cell \(0\) stays there, so every tape reachable from an initial configuration keeps this marker invariant (statements about arbitrary tapes assume it explicitly). A tape has output \(y \in \{ 0,1\} ^*\) when cells \(1, \dots , |y|\) hold the bits of \(y\) and cell \(|y| + 1\) is blank.

A language is a set of finite binary strings, \(L \subseteq \{ 0,1\} ^*\).

A configuration of a machine with state set \(Q\) and \(k\) work tapes consists of a state, an input tape, \(k\) work tapes, and an output tape, each a named field. The initial configuration on input \(x\) is in the start state, with \(x\) written from cell \(1\) of the input tape, every other tape empty, and every head at cell \(0\).

A deterministic Turing machine with \(k\) work tapes consists of a finite state type \(Q\) with decidable equality, a start state and a halt state, and a transition function

that must move right every head reading \(\triangleright \). One step applies \(\delta \) to the current state and the symbols under the input head, the \(k\) work heads, and the output head, writes on the work and output tapes, and moves all heads; the halt state has no successor. The relation \(c \to ^t c'\) holds when \(c'\) is reached from \(c\) in exactly \(t\) steps, and \(c \to ^* c'\) is its reflexive–transitive closure.

A nondeterministic Turing machine has the same data as a deterministic one except that it has two transition functions \(\delta _0, \delta _1\), each subject to the same rule at \(\triangleright \). Its execution is defined only through the trace: given a choice sequence \(r \in \{ 0,1\} ^T\), run \(T\) steps, using \(\delta _{r_i}\) at step \(i\), and stay put once the halt state is reached. The same structure serves as a probabilistic machine, with \(r\) read as random bits. A deterministic machine embeds by taking \(\delta _0 = \delta _1 = \delta \).

A deterministic machine \(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\) (Arora–Barak Definition 1.2).

A deterministic machine \(M\) computes \(f : \{ 0,1\} ^* \to \{ 0,1\} ^*\) in time \(T\) if on every input \(x\) it halts within \(T(|x|)\) steps and its output tape has output \(f(x)\). It computes \(f\) if it does so for some \(T\).

A nondeterministic machine \(N\) accepts \(x\) in time \(T\) if some choice sequence of length \(T\) leads to the halt state with output cell \(1\) equal to \(1\). It decides \(L\) in time \(T\) if every trace on every input \(x\) has halted after \(T(|x|)\) steps, and \(x \in L\) exactly when \(N\) accepts \(x\) in time \(T(|x|)\) (Arora–Barak Definition 2.1). Rejection is the absence of an accepting path; it does not require output \(0\).

For a machine \(N\), input \(x\), and clock \(T\), the acceptance probability is the rational number

and the probability of output \(y\) is defined the same way with the output condition in place of acceptance. Both are meaningful when every trace has halted by time \(T\).

A deterministic machine \(M\) halts on a program \(p\) (within time \(t\)) if the run from the initial configuration on \(p\) reaches the halt state (within \(t\) steps). It produces \(y\) on \(p\) (within time \(t\)) if moreover the output tape of the halted configuration has output \(y\). The bounded evaluator \(\mathrm{run}(c, t)\) is the configuration after \(t\) steps, standing still once halted.

For predicates \(\mathit{pre}, \mathit{post}\) on (input tape, work tapes, output tape) and a bound \(b \in \mathbb {N}\), the triple \(\{ \mathit{pre}\} \, M\, \{ \mathit{post}\} _b\) holds if \(M\), started in its start state on any tapes satisfying \(\mathit{pre}\), halts within \(b\) steps on tapes satisfying \(\mathit{post}\). The unbounded triple drops the step bound.

On machines with the same \(k\) work tapes: \(\mathrm{seq}(M_1, M_2)\) runs \(M_1\) to completion and then \(M_2\) on the same tapes; \(\mathrm{if}(M_t, M_1, M_0)\) runs the test \(M_t\), rewinds the output head, and runs \(M_1\) if output cell \(1\) holds \(1\) and \(M_0\) otherwise; \(\mathrm{loop}(M_b, M_t)\) alternates the body and the test, rewinding the output head after each test, and halts once the test leaves \(1\) in output cell \(1\); \(\mathrm{complement}(M)\) runs \(M\), rewinds the output head, and exchanges \(0\) and \(1\) in output cell \(1\) (a blank stays blank). In \(\mathrm{seq}\) (from \(M_1\) to \(M_2\)), in \(\mathrm{loop}\) (from the body to the test), and in \(\mathrm{if}\) (from the branch to the final halt state), the handover is a single step in which every head reading \(\triangleright \) moves one cell right, the other heads stay, and no tape cell changes except that a \(\triangleright \) outside cell \(0\) would be overwritten by a blank. After the test in \(\mathrm{if}\) and \(\mathrm{loop}\) the handover takes several steps: one such step; then steps that move the output head left one cell at a time until it reads \(\triangleright \), and then one cell right; and a last step that reads the output cell under the head (cell \(1\) when \(\triangleright \) appears on the output tape only at cell \(0\)) and enters the chosen branch, the body, or the halt state. In each of these steps every input or work head reading \(\triangleright \) moves one cell right and the others stay, and cells change only as in the single-step handover. The machine \(\mathrm{union}(M_1, M_2)\), with \(M_i\) on \(k_i\) work tapes, has \(k_1 + 1 + k_2\) work tapes: it runs \(M_1\) with its output redirected to work tape \(k_1\), halts with \(1\) in output cell \(1\) if cell \(1\) of that work tape holds \(1\), and otherwise rewinds the input and runs \(M_2\) on the last \(k_2\) work tapes and the real output tape.

A deterministic machine \(U\) simulates \(M\) under a compiler \(c : \{ 0,1\} ^* \to \{ 0,1\} ^*\) if for every program \(p\): \(U\) halts on \(c(p)\) if and only if \(M\) halts on \(p\), and for every \(y\), \(U\) produces \(y\) on \(c(p)\) if and only if \(M\) produces \(y\) on \(p\).

\(U\) simulates \(M\) under \(c\) in time \(\tau : \{ 0,1\} ^* \times \mathbb {N} \to \mathbb {N}\) if whenever \(M\) halts on \(p\) (resp. produces \(y\) on \(p\)) within \(t\) steps, \(U\) halts on \(c(p)\) (resp. produces \(y\) on \(c(p)\)) within \(\tau (p, t)\) steps. The compiler has additive overhead \(C\) if \(|c(p)| \le |p| + C\) for all \(p\). The clock \(\tau \) is polynomial if \(\tau (p, t) \le a (|p| + t + 1)^e\) for some constants \(a, e\).

A function \(f : \{ 0,1\} ^* \to \{ 0,1\} ^*\) is computable if some deterministic machine, with any number of work tapes, computes \(f\).

A deterministic machine \(U\) is universal if for every \(k\) and every machine \(M\) with \(k\) work tapes there is a computable compiler \(c\) such that \(U\) simulates \(M\) under \(c\). It is efficiently universal for an admissibility predicate on clocks if for every such \(M\) there are a computable compiler \(c\), a constant \(C\), and a clock \(\tau \) such that \(U\) simulates \(M\) under \(c\), \(c\) has additive overhead \(C\), \(U\) simulates \(M\) under \(c\) in time \(\tau \), and \(\tau \) is admissible; it is efficiently universal when the predicate is polynomiality. Computability of \(c\) is essential: without it a machine that copies its input after a leading \(0\) and diverges after a leading \(1\) would be universal, with a compiler that consults the source machine’s halting behavior and output.

The universal machine \(\mathcal{U}\) has six work tapes and is \(\mathrm{seq}(\mathrm{init}, \mathrm{seq}(\mathrm{loop}(\mathrm{body}, \mathrm{haltTest}), \mathrm{extract}))\). On input \(\langle \alpha , x \rangle \) it parses the description \(\alpha \) of a one-work-tape machine, simulates one step per loop iteration, tests for the halt state, and finally copies the simulated output tape to its own output tape.

\(T : \mathbb {N} \to \mathbb {N}\) is time-constructible if \(T(n) \ge n\) for all \(n\) and some deterministic machine computes \(x \mapsto \mathrm{bin}(T(|x|))\) (least significant bit first) in time \(O(T(n))\) (Arora–Barak Definition 1.12). The formalized hierarchy theorem does not use this notion.

\(g\) is clock-constructible if there are an eight-work-tape machine \(M\) and a constant \(C\) such that, for every input \(x\) and every starting layout in which the input tape holds \(x\) with its head at cell \(1\), every work head is at a cell \(\ge 1\) not reading \(\triangleright \), work tapes \(5\) and \(6\) are blank with their heads at cell \(1\), and the output head is at cell \(1\) with \(\triangleright \) at cell \(0\) and nowhere else, \(M\) started in its start state halts within \(C (g(|x|) + |x| + 1)\) steps with: work tape \(6\) holding the unary clock of length \(g(|x|)\) (cells \(1, \dots , g(|x|)\) equal to \(1\), the rest blank, head at cell \(1\)); every other work tape exactly as it started (so the scratch tape \(5\) is again blank); the input head back at cell \(1\); and the output head at cell \(1\) with \(\triangleright \) still at cell \(0\) and nowhere else. The layout is pinned to the diagonalizer that consumes it.

A program is a list of instructions over registers \(R_0, R_1, \dots \) holding natural numbers: immediate load, \(\mathrm{add}\), truncated \(\mathrm{sub}\), \(\mathrm{mul}\), indirect \(\mathrm{load}\) (\(R_d := R_{R_a}\)) and \(\mathrm{store}\) (\(R_{R_a} := R_s\)), conditional and unconditional jumps, and \(\mathrm{halt}\); a program counter past the end halts. On input \(x\), \(R_0 = |x|\), \(R_{i+1} = x_i\), and all other registers are \(0\). Each instruction costs \(1\) plus bit lengths of the values it touches: the constant of an immediate load; both operands and the result for \(\mathrm{add}\) and \(\mathrm{mul}\); both operands for \(\mathrm{sub}\) (whose result is no longer than its first operand); the runtime address and the value moved for indirect \(\mathrm{load}\) and \(\mathrm{store}\); the tested register for a conditional jump; nothing more for \(\mathrm{jmp}\) and \(\mathrm{halt}\). Register indices and jump targets written in the program are not charged. The logarithmic time of a run is the total cost of its non-halted steps, and its unit time is the number of those steps. Space is the peak, over the configurations visited, of the total bit length of the addresses and contents of the nonzero registers.

A program decides \(L\) in time \(T\) if on every input \(x\) it halts after logarithmic cost at most \(T(|x|)\) with \(R_0 = 1\) if \(x \in L\) and \(R_0 = 0\) otherwise; deciding in space \(S\) bounds peak space instead. Then \(\mathsf{DTIME}_{\mathrm{RAM}}(T)\) and \(\mathsf{DSPACE}_{\mathrm{RAM}}(S)\) are the languages decided in time \(O(T)\) and space \(O(S)\), and \(\mathsf{P}_{\mathrm{RAM}} = \bigcup _k \mathsf{DTIME}_{\mathrm{RAM}}(n^k)\).