175 Complexity — Universal
175.1 Overview
This module provides the universal Turing machine (Arora–Barak, Theorem 1.9 and §1.4.1): a single machine simulating any coded machine with multiplicative overhead depending only on the code, the quadratic corollary for total functions of arbitrary binary machines, and a time-bounded (clocked) universal machine that reports success or timeout against a supplied deadline. Most declarations build the clocked simulator: a prefix parser that separates the clock from the code, a table interpreter with exact step counts that stops just before each simulated transition, a fixed-width binary countdown, and an output-buffering wrapper that withholds emissions until the simulated machine is known to halt in budget. Throughout, bit strings are written over \(\{ 0,1\} \) (\(1\) for true, \(0\) for false); the pair encoding \(\langle \alpha , x\rangle \) of two bit strings lists each bit of \(\alpha \) twice, then the unequal delimiter pair \(01\), then \(x\) verbatim; and the buffer tape of a string \(w\) is the two-way infinite tape holding \(w\) in cells \(0,\dots ,|w|-1\) and blanks elsewhere.
175.2 Declarations
For every effective machine-coding scheme there is a single finite-tape machine \(U\) over the alphabet \(\{ 0,1\} \) such that for every code string \(\alpha \) there is a constant \(C\) (depending on \(\alpha \)) with the following two properties for every input string \(x\). Forward: whenever the coded machine denoted by \(\alpha \) halts on \(x\) within \(t\) steps with output \(w\), the machine \(U\) on the pair encoding \(\langle \alpha , x\rangle \) (each bit of \(\alpha \) doubled, the delimiter \(01\), then \(x\) verbatim) halts with the same output \(w\) within \(C \cdot (t+1)\) steps. Converse: every output that \(U\) produces on \(\langle \alpha , x\rangle \) upon halting is an output the denoted machine produces on \(x\) upon halting, so divergence is preserved.
For every effective machine-coding scheme there is a single machine \(U\) over \(\{ 0,1\} \) with the following property: whenever a finite-tape binary machine computes a total function \(f\) on bit strings within a time bound \(T \colon \mathbb {N} \to \mathbb {N}\), there are a code string \(\alpha \) and a constant \(C\) such that for every input \(x\), the machine \(U\) on the pair encoding \(\langle \alpha , x\rangle \) halts with output \(f(x)\) within \(C \cdot (T(|x|)+1)^2\) steps.
The four-tape table interpreter of the universal-machine construction, modified so that every control state holding a fully decoded transition record halts immediately instead of applying the record; on all other control states its transition function agrees with the original interpreter.
Consider an interpreter evaluation configuration, whose four work tapes are: a table tape holding the buffer of a bit string \(T\) with cursor \(p\), a state tape \(\sigma \colon \mathbb {Z} \to \{ 0,1,\text{blank}\} \) with cursor \(s\), and a mirrored work tape and a boundary-marker tape taken from a base configuration. The four symbols under its work heads are, in order, the table symbol at \(p\), the state symbol \(\sigma (s)\), and the two symbols read on the corresponding tapes of the base configuration.
Applying an administrative interpreter action — one that moves the table cursor by \(d_t \in \{ -1,0,1\} \), optionally writes a symbol at the state-tape cursor, moves the state cursor by \(d_s\), and passes to a control state \(q'\) — to an interpreter evaluation configuration changes exactly the two designated cursors and, when a write is present, the state-tape cell at the cursor; the input head, the mirrored data, and the accumulated output are unchanged.
If, on the symbols read in an interpreter evaluation configuration, the transition function of the stopped table interpreter returns the administrative action with table move \(d_t\), optional state-tape write, state move \(d_s\), and next control \(q'\), then one machine step from that configuration yields exactly the evaluation configuration with control \(q'\), table cursor shifted by \(d_t\), and state tape and state cursor updated accordingly.
For all bit strings \(l\) and \(r\) and every bit \(b\), the buffer tape of the concatenation of \(l\), the single bit \(b\), and \(r\) reads the symbol \(b\) at position \(|l|\).
Suppose the stopped table interpreter is in its table-rewind phase with the table cursor at \(j-1\), where \(j\) is at most the table length. Then exactly \(j+1\) steps bring it to the count-parsing phase with the table cursor at \(0\), leaving the state tape, the mirrored data, the input head, and the accumulated output unchanged.
Suppose the table holds, starting at the cursor position \(|l|\), the doubling \(b_1 b_1 b_2 b_2 \cdots \) of a count string of \(n\) bits followed by the delimiter pair \(01\). Then the count-parsing phase of the stopped table interpreter traverses this field in exactly \(2n+2\) steps, advancing the cursor past the delimiter and entering the initial-state copier (when copying was requested) or the initial-state skipper; no binary arithmetic on the count’s value is performed.
Writing the symbol \(1\) into cell \(n+1\) of the unary state tape representing \(n\) (a marker \(0\) in cell \(0\) followed by \(n\) ones) yields the unary state tape representing \(n+1\).
The unary state tape representing \(n\) (a marker \(0\) in cell \(0\) followed by \(n\) ones) reads a blank at cell \(n+1\).
Suppose the state tape holds the marker symbol \(0\) at cell \(0\) and no cell at a positive position holds \(0\), and suppose the current control of the stopped table interpreter moves the state head left on every non-marker read while, on reading the marker, it moves right once and transfers to a designated continuation control \(q'\). Then from state cursor \(j \in \mathbb {N}\) the interpreter reaches \(q'\) with state cursor \(1\) in exactly \(j+1\) steps, without changing any tape contents, the input head, or the output; the premise is independent of whether the traversed cells are erased blanks or retained unary symbols.
If the table holds \(n\) ones followed by a zero starting at the cursor position \(|l|\), then the initial-state-skipping phase of the stopped table interpreter traverses this unary field in exactly \(n+1\) steps and enters record-group selection with the table cursor at \(|l|+n+1\).
Suppose the current control \(q\) of the stopped table interpreter appends one unary symbol to the state tape and advances both cursors whenever the table reads \(1\), and on reading \(0\) transfers to a continuation control \(q'\) with a designated final table move. If the table holds \(n\) ones followed by a zero at cursor position \(|l|\), then \(n+1\) steps transform the unary state tape for \(j\) (state cursor \(j+1\)) into the unary state tape for \(j+n\) (state cursor \(j+n+1\)), with the table cursor ending at \(|l|+n\) plus the final move. This single gadget serves both initial-state extraction and successor-state replacement.
Writing a single symbol \(b\) into cell \(0\) of the all-blank tape yields the buffer tape of the one-character string \(b\).
The configuration of the stopped table interpreter at entry: control in the start phase, the captured table held on the first work tape as a buffer with its cursor at the right blank, three blank auxiliary tapes, empty output, and the input head already parked at a given position of the input.
The inactive part of an interpreter configuration during initialization: the input head parked at a given position, a blank mirrored work tape, the virtual-input left-boundary marker installed at cell \(0\) of its tape with its head at \(1\) (also correct for an empty input suffix), and empty output.
The first step of the stopped table interpreter from its entry configuration installs the two permanent markers (the state-tape origin marker and the virtual-input boundary marker) and enters the unconditional table rewind with the table cursor on the last table cell.
Suppose the captured table \(T\) is the pair encoding of a count string of \(m\) bits with a body consisting of \(n\) ones, a terminator zero, and a record region. Then exactly \(|T| + 2m + 2n + 7\) steps of the stopped table interpreter bring the entry configuration to the main simulation phase, with the table cursor at \(2m + 2 + n + 1\) (just past the header) and the state tape holding the unary representation of \(n\) with cursor \(1\); every intermediate configuration keeps the input head fixed and the output empty, and no transition-record lookup is involved.
In the fixed-field-skipping phase of the stopped table interpreter, with current field index \(i\) and \(n\) further fields remaining (so \(i + n = 7\)), exactly \(n+1\) steps advance the table cursor by \(n+1\) cells and enter the unary-tail scanner; no tape content is inspected or modified.
If the table holds \(n\) ones followed by a zero at cursor position \(|l|\), the unary-skipping phase of the stopped table interpreter traverses them in exactly \(n+1\) steps, ending with the cursor at \(|l|+n+1\); on the terminator it completes the skip request when the bounded record counter is zero, and otherwise decrements the counter and re-enters fixed-field skipping.
If a complete serialized transition record — eight fixed bits followed by a unary successor field and its terminator — occupies the table starting at the cursor, then the skipping phase of the stopped table interpreter traverses it in exactly its serialized length, decrementing the bounded record counter, or completing the skip request when the counter is zero, with the cursor moved past the record.
If the table holds, at the cursor, the concatenated serializations of a nonempty list of transition records whose length is one more than the bounded record counter, then the skipping phase of the stopped table interpreter traverses all of them in exactly the total serialized length and finishes in the requested continuation with the cursor past the last record; no extra transition occurs between consecutive records.
Suppose the table holds, at the cursor, the concatenated records of a list of \(g\) state groups, each consisting of nine records, and the state tape holds a partially erased unary state whose remaining ones number exactly \(g\). Then in exactly \(g\) plus the total serialized length plus one steps, the stopped table interpreter erases one unary state symbol per group, skips all of the groups’ records, and enters the state rewind, with the table cursor past the traversed records and all erasures recorded on the state tape.
Suppose the table holds a word \(b\) of eight bits starting at position \(|l|\), the action-reading phase of the stopped table interpreter is at field index \(i\) with \(n = 7-i\) fields left, and the accumulated eight-bit register agrees with \(b\) on all indices below \(i\). Then exactly \(n+1\) steps fill the register with all of \(b\) and enter the successor-decoding phase, with the table cursor at \(|l|+8\).
The number of interpreter steps used to decode a record’s successor field and install and rewind its unary state before the action is applied: \(1\) for a halting successor, and \(2q + 4\) for a live successor of index \(q\).
Suppose the table holds, at the cursor, the unary successor field of a record (its number of ones encoding the optional successor state) followed by its terminator, and the state tape is the unary tape for \(0\) with cursor \(1\). Then within exactly the successor-preparation cost, the stopped table interpreter installs the unary representation of the successor index (or of \(0\) in the halting case) on the state tape with cursor \(1\) and enters the pending-action phase carrying the eight decoded bits and the halting flag, with the table cursor stopped on the field’s terminator.
For a coded one-work-tape binary machine and a state \(q\), the list of the nine transition actions of \(q\), one for each pair of an optional input read and an optional work read, ordered with the input read (blank, \(0\), \(1\)) as the major key and the work read (in the same order) as the minor key.
For every coded machine, state \(q\), and pair of optional input and work reads, the nine-action list of \(q\) has length \(9\), and its entry at the record index determined by the two reads (a number in \(\{ 0,\dots ,8\} \)) is exactly the machine’s transition action for \(q\) on those reads.
The header of a coded machine’s serialization: the doubled binary state count with its delimiter pair, followed by the unary initial-state field (as many ones as the initial state’s index) and its terminator zero; the transition records are excluded.
The canonical serialization of a coded machine equals its header followed by the concatenation, over its states in increasing order, of the serialized nine-action record lists of each state.
For every coded machine, state \(q\), and pair of optional input and work reads, the serialization splits as: the header, then the record groups of the \(q\) states preceding \(q\) (each a list of nine records), then the records of \(q\)’s group preceding the read offset selected by the two reads, then the serialized record of the machine’s transition action for \(q\) on those reads, then a remainder.
Decoding the four fixed two-bit pairs of a transition action’s eight-bit serialization recovers, in order, the action’s input-head movement, its optional work-tape write, its work-head movement, and its optional emission.
Suppose the table holds, at the cursor, the concatenated records of \(g\) preceding state groups (nine records each) followed by the records preceding the selected read offset, and the state tape is the unary tape for \(g\) with cursor \(1\). Then in exactly \(2g\) plus the total serialized length of the traversed records plus \(3\) steps, the stopped table interpreter destructively counts down the unary state while skipping its groups, rewinds the erased state tape, skips the read-offset prefix (entering the action reader directly when the offset is zero), and arrives in the action-reading phase with a cleared register, the table cursor at the selected record, and the state tape reset to the unary tape for \(0\).
For any multi-tape machine, if running \(s\) steps from a configuration \(a\) yields \(b\) and running \(t\) steps from \(b\) yields \(c\), then running \(s+t\) steps from \(a\) yields \(c\).
Let \(M\) be a coded machine, let \(\mathrm{src}\) be a configuration of \(M\), and let \(a\) be a transition action of \(M\). One step of the (unstopped) four-tape table interpreter from the pending-action evaluation configuration — built over the interpreter checkpoint of \(\mathrm{src}\), carrying the eight decoded bits of \(a\) and the halting flag of its successor, with the serialized table, any table cursor \(p\), and the unary tape of the successor index installed — equals exactly the interpreter checkpoint of the configuration obtained by applying \(a\) to \(\mathrm{src}\), with table cursor \(p\); this includes the correct virtual-input head movement, optional write, emission, and the halting case.
Let \(M\) be a coded machine with serialization of length \(L\) and state count \(N+1\), let \(\mathrm{src}\) be a non-halted configuration of \(M\), and let the table cursor \(p\) satisfy \(p \le L\). Then there exist a duration \(d \le 3L + 5(N+1) + 20\), a new cursor \(p' \le L\), and a configuration \(\mathrm{ready}\) whose control is a pending-action state, such that the stopped table interpreter runs from the interpreter checkpoint of \(\mathrm{src}\) to \(\mathrm{ready}\) in exactly \(d\) steps, and one step of the unstopped interpreter from \(\mathrm{ready}\) is the interpreter checkpoint of the configuration obtained by one step of \(M\) from \(\mathrm{src}\), with table cursor \(p'\).
The physical input region occupied by a clock string \(b\) under the nested pair encoding: each bit of \(b\) repeated four times, followed by the four delimiter cells \(0011\).
For all bit strings \(b\), \(\alpha \), \(x\), the nested pair encoding \(\langle \langle b, \alpha \rangle , x\rangle \) equals the physical clock prefix of \(b\) (each bit quadrupled, then the four cells \(0011\)) followed by the pair encoding \(\langle \alpha , x\rangle \).
The physical clock prefix of a string \(b\) has length \(4|b| + 4\).
The finite control of the clock–code prefix parser: four phases that walk the four physical copies of each clock bit, an end-of-clock phase for the separator, and two phases that walk the doubled code bits.
A one-work-tape machine over \(\{ 0,1\} \) that scans the nested pair encoding from the left: it stores each undoubled clock bit on its work tape (one write per four input cells), then emits each undoubled code bit as output (one emission per two input cells), and halts on the outer separator, before reading any of the input suffix.
The configuration of the prefix parser on the nested pair encoding \(\langle \langle b, \alpha \rangle , x\rangle \) with a given control state and input position, the captured clock string held on its work tape as a buffer with head at the right blank, and a given accumulated output.
For all bit strings \(b\), \(\alpha \), \(x\), the nested pair encoding \(\langle \langle b, \alpha \rangle , x\rangle \) has length \(4|b| + 2|\alpha | + 6 + |x|\).
For every \(j \lt |b|\) and every \(r \lt 4\), cell \(4j + r\) of the nested pair encoding \(\langle \langle b, \alpha \rangle , x\rangle \) holds the clock bit \(b_j\).
For every \(r \lt 4\), cell \(4|b| + r\) of the nested pair encoding \(\langle \langle b, \alpha \rangle , x\rangle \) holds the \(r\)-th symbol of the four-cell separator \(0011\).
Suppose the prefix parser’s transition in control \(q\), on the input symbol found at physical position \(p\) of the nested pair encoding, moves the input head right, writes nothing to the work tape, optionally emits one bit, and passes to a control \(q'\). Then one machine step from the corresponding parser configuration advances the physical input position by one, appends the optional emission to the output, keeps the stored clock unchanged, and enters \(q'\).
In the fourth phase of a clock bit \(b\), one step of the prefix parser advances the input head one cell and appends the single bit \(b\) to the clock string stored on its work tape, returning to the first clock phase with no output.
For every \(j \le |b|\), running the prefix parser \(4j\) steps from its initial configuration on the nested pair encoding \(\langle \langle b, \alpha \rangle , x\rangle \) stores exactly the first \(j\) clock bits on its work tape, leaves the output empty, and places the input head just past the \(4j\) consumed cells, still in the first clock phase.
Running the prefix parser \(4|b| + 4\) steps from its initial configuration on the nested pair encoding \(\langle \langle b, \alpha \rangle , x\rangle \) consumes the entire quadrupled clock and its four separator cells, stores exactly \(b\) on the work tape, produces no output, and enters the code-extraction phase.
For every \(j\), cell \(4|b| + 4 + j\) of the nested pair encoding \(\langle \langle b, \alpha \rangle , x\rangle \) equals cell \(j\) of the inner pair encoding \(\langle \alpha , x\rangle \).
For every \(j \lt |\alpha |\), cells \(2j\) and \(2j+1\) of the pair encoding \(\langle \alpha , x\rangle \) both hold the code bit \(\alpha _j\).
Cells \(2|\alpha |\) and \(2|\alpha | + 1\) of the pair encoding \(\langle \alpha , x\rangle \) hold \(0\) and \(1\) respectively.
For every \(j \le |\alpha |\), running the prefix parser \(4|b| + 4 + 2j\) steps from its initial configuration on the nested pair encoding \(\langle \langle b, \alpha \rangle , x\rangle \) keeps the stored clock \(b\) intact, emits exactly the first \(j\) code bits as output, and remains in the code-extraction phase with the input head just past the consumed cells.
Running the prefix parser \(4|b| + 2|\alpha | + 6\) steps from its initial configuration on the nested pair encoding \(\langle \langle b, \alpha \rangle , x\rangle \) halts it with the full clock \(b\) stored on the work tape, output exactly \(\alpha \), and the input head parked at the start of the suffix region holding \(x\); both delimiters are consumed, also when \(b\) or \(\alpha \) is empty.
The little-endian numeric value of a fixed-width Boolean word: the empty word has value \(0\), and the word with first bit \(b\) and tail \(w\) has value \(2 \cdot \mathrm{value}(w) + b\).
For every natural number \(t\), the little-endian value of the binary representation of \(t\) is \(t\).
Fixed-width binary subtraction of an incoming borrow flag from a little-endian word: each output bit is the exclusive or of the corresponding input bit with the propagated borrow, the borrow propagates exactly through the zero bits, and the result is the final (underflow) borrow flag together with a word of the same width.
Subtracting a cleared borrow flag from a word leaves the word unchanged and reports no underflow.
For every incoming borrow flag and word, the word returned by the fixed-width borrow subtraction has the same length as the input word.
Subtracting a set borrow flag from a word underflows if and only if the word’s little-endian value is \(0\).
If a word has positive little-endian value, then the value of the word obtained by subtracting a set borrow flag is exactly one less than the value of the original word.
The finite control of the timed interpreter: a working copy of the table interpreter’s control, clock phases (rewind and borrow) that retain a selected action’s eight decoded bits and halting flag while the countdown is serviced, an execute phase, and three output phases (emission start, buffer rewind, and flush).
The assembly of a function on six tape indices from four core values, a clock value, and a buffer value: indices \(0\) through \(3\) map to the core values, index \(4\) to the clock value, and index \(5\) to the buffer value.
The lift of a four-tape interpreter action to six tapes: the four core lanes act as before, the clock lane is untouched, any emission is written to the output-buffer lane (advancing its head) instead of being emitted, and a halting successor is redirected to the emission-start phase so that the machine stays live.
A six-tape action that leaves the four core lanes and the input head untouched, performs a designated optional write and move on the clock lane and on the output-buffer lane, optionally emits one real output bit, and passes to a designated control.
The six-tape interpreter with a countdown clock: it follows the table interpreter, buffering all emissions, until a decoded action is pending; it then rewinds the clock lane and performs one fixed-width borrow pass. A successful borrow executes the retained action; an underflow halts the machine emitting only the timeout tag \(0\). When the simulated machine halts, the machine emits the success tag \(1\) and flushes the buffered output before halting.
The six-tape configuration representing a four-tape interpreter configuration together with a clock word: the four core lanes are copied, the clock lane holds the clock word as a buffer with head at its right blank, the buffer lane holds the four-tape configuration’s accumulated output, and the real output is empty; a halted four-tape control maps to the emission-start phase.
For every control state that is not a pending-action state, the transition function of the stopped table interpreter agrees with that of the original table interpreter on all reads.
If the stopped table interpreter has not halted after \(t\) steps from a configuration, then it has not halted after any \(s \le t\) steps from that configuration (halting is absorbing).
If the stopped table interpreter has not halted after \(t\) steps from a configuration, then at every time \(s \lt t\) its control is not a pending-action state, because the stopped interpreter halts one step after reaching such a state.
Restricting the six-lane assembly of four core values, a clock value, and a buffer value to the first four indices returns the four core values.
Applying the six-tape lift of a four-tape interpreter action to the six-tape lift of a four-tape configuration (with any clock word) equals the lift of the configuration obtained by applying the action: the clock word is unchanged and any emission is captured on the buffer lane, including an emission on the action’s halting transition.
For every live four-tape configuration whose control is not a pending-action state, one step of the timed interpreter from its six-tape lift (with any clock word) equals the lift of one step of the stopped table interpreter, with the same clock word.
If the stopped table interpreter has not halted after \(t\) steps from a four-tape configuration, then \(t\) steps of the timed interpreter from the six-tape lift of that configuration equal the lift of the \(t\)-step stopped run, with an unchanged clock word; no countdown or output phase is visited in the interior of the run.
A configuration in which one designated work tape holds a finite zipper — a frontier position, a stack of processed cells, and a list of unprocessed cells — while every other component (the remaining tapes, all other heads, the input position, and the output) is taken from a base configuration.
An action that writes an optional symbol and moves on exactly one designated work tape, leaves the input head, the output, and all other work tapes stationary, and passes to a given control state.
In a single-active-lane configuration, the active lane reads the first entry of the unprocessed zipper list, or a blank when that list is empty.
Applying a right-moving single-lane action that writes a symbol \(b\) to a single-active-lane configuration whose unprocessed list begins with a cell \(a\) consumes \(a\), pushes \(b\) onto the processed stack, advances the frontier by one, and passes to the designated control; all inactive data is unchanged.
Suppose a machine’s transitions, on a family of control states indexed by a register type, always perform a right-moving single-lane write determined by a local visit function of the register and the symbol read on the designated lane. Then running the machine for exactly the length of a word laid out on that lane’s zipper computes the left fold of the visit function over the word: the final control carries the folded register, the frontier advances by the word’s length, the processed stack holds the rewritten word reversed, and all inactive tapes are unchanged.
A timed administrative action that writes and moves only on the clock lane coincides with the generic single-lane action on lane \(4\) of the six-tape machine.
The fixed-width borrow subtraction equals the left fold of the local rule sending a carry flag \(c\) and a bit \(b\) to the new carry \(c \wedge \lnot b\) and the output bit \(b \oplus c\).
From the borrow phase with a given carry flag and the clock word laid out on the clock lane’s zipper, the timed interpreter processes the word in exactly its length: the final control carries the resulting underflow flag, the processed stack holds the borrowed word, and neither the four simulation lanes nor the buffered output is touched.
Moving the frontier of a finite zipper across a segment \(w\) — pushing the reversal of \(w\) onto the processed stack and advancing the frontier by \(|w|\) — leaves the represented tape unchanged.
The buffer tape of a word equals the zipper with frontier \(0\), empty processed stack, and the word as the unprocessed list.
The buffer tape of a word also equals the zipper with frontier at the word’s length, the reversed word as the processed stack, and an empty unprocessed list.
The configuration obtained from a base six-tape configuration by overriding only the finite control and the clock lane, whose contents become the buffer of a given word with the head at a given position.
Suppose that, whenever the clock lane reads its designated symbol, the timed interpreter’s transition in control \(q\) is a pure clock move by \(d \in \{ -1,0,1\} \) (no writes, no emission) into a control \(q'\). Then one step from the clock-phase configuration moves only the clock head by \(d\) and enters \(q'\).
For every \(j\) at most the clock word’s length, from the clock-rewind phase with the clock head at \(j-1\), exactly \(j+1\) steps of the timed interpreter reach the borrow phase with the borrow flag set and the clock head at \(0\); the retained action bits and halting flag are unchanged.
From the borrow phase with a given carry flag and the clock head at \(0\), exactly as many steps of the timed interpreter as the clock word’s length replace the word by its borrow subtraction, ending at the right blank with the resulting underflow flag in the control; the word’s width is preserved.
From the six-tape lift of a four-tape configuration whose control is a pending-action state, one step of the timed interpreter enters the clock-rewind phase — retaining the action’s decoded bits and halting flag — with the clock head moved to the last clock bit, and without applying any source transition.
From the six-tape lift of a pending-action configuration with clock word \(w\), exactly \(2|w| + 2\) steps of the timed interpreter complete the clock rewind and the borrow pass, reaching the borrow phase at the right blank with the subtracted word and its underflow flag in the control.
From the six-tape lift of a pending-action configuration, with the control replaced by the execute phase, one step of the timed interpreter applies the retained source action: the result equals the lift of one step of the unstopped table interpreter from the four-tape configuration, with the clock word unchanged.
If the clock word \(w\) has positive little-endian value, then from the six-tape lift of a pending-action configuration, exactly \(2|w| + 4\) steps of the timed interpreter decrement the budget once and apply the retained action: the result is the lift of one step of the unstopped table interpreter, with clock word the borrow subtraction of \(w\).
If the clock word \(w\) has little-endian value \(0\), then after \(2|w| + 3\) steps of the timed interpreter from the six-tape lift of a pending-action configuration, the machine has halted with real output exactly the single timeout tag \(0\), regardless of any emissions buffered so far.
The configuration obtained from the six-tape lift of a four-tape configuration and a clock word by overriding the finite control, the output-buffer head position, and the real output; all simulation and clock tapes are retained.
Suppose that, whenever the output-buffer lane reads its designated symbol, the timed interpreter’s transition in control \(q\) is a pure buffer move by \(d \in \{ -1,0,1\} \) with an optional real emission. Then one step from the output-phase configuration moves only the buffer head by \(d\), appends the optional emission to the real output, and passes to the designated control.
For every \(j\) at most the buffered output’s length, from the buffer-rewind phase with the buffer head at \(j-1\), exactly \(j+1\) steps of the timed interpreter reach the flush phase with the buffer head at \(0\), emitting the success tag \(1\) at the left blank before any data bit.
If the buffered output splits as a processed prefix \(l\) followed by a remainder \(r\), with the buffer head at \(|l|\), then the flush phase of the timed interpreter emits exactly the bits of \(r\), in order, in \(|r| + 1\) steps and halts at the right blank without a further emission.
From the six-tape lift of a halted four-tape configuration whose buffered output is a word \(w\), exactly \(2|w| + 3\) steps of the timed interpreter halt the machine with real output the success tag \(1\) followed by exactly \(w\).
After \(4|b| + 2|\alpha | + 5\) steps on the nested pair encoding \(\langle \langle b, \alpha \rangle , x\rangle \) — one step before consuming the final separator cell — the prefix parser has not halted.
At every time strictly before \(4|b| + 2|\alpha | + 6\) steps on the nested pair encoding \(\langle \langle b, \alpha \rangle , x\rangle \), the prefix parser has not halted.
The buffered composition of the prefix parser with the coding scheme’s canonizer: the parser extracts the code string from the nested pair encoding, and only that extracted code is supplied as virtual input to the canonizer.
The tape index of the composed clock-preserving canonizer corresponding to the prefix parser’s unique work tape, on which the extracted clock word is retained.
On the nested pair encoding \(\langle \langle b, \alpha \rangle , x\rangle \), exactly \(4|b| + 3|\alpha | + 8\) steps of the composed clock-preserving canonizer complete the parse and hand the extracted code \(\alpha \) to the canonizer in its initial configuration, with the clock word \(b\) preserved on its lane (head at \(|b|\)) and the physical input head parked at the start of the suffix region.
For every \(t\), running the composed clock-preserving canonizer \(4|b| + 3|\alpha | + 8 + t\) steps on the nested pair encoding equals, for some internal rewind flag, the buffered second-phase configuration of the canonizer run for \(t\) steps on virtual input \(\alpha \); the physical input head and the retained clock word \(b\) remain stationary.
After \(4|b| + 3|\alpha | + 8\) plus the canonizer’s time bound at \(|\alpha |\) steps on the nested pair encoding, the composed clock-preserving canonizer has halted; its output is the serialization of the machine decoded from \(\alpha \), its input head is parked at position \(4|b| + 2|\alpha | + 7\), and its retained clock lane still holds the buffer of \(b\) with head at \(|b|\).
The answer of a source configuration of a coded machine after a deadline of \(t\) steps: the success tag \(1\) followed by the accumulated output when the machine has halted within \(t\) steps, and the single timeout tag \(0\) otherwise.
Let \(M\) be a coded machine with serialization of length \(L\) and state count \(N+1\), let \(\mathrm{src}\) be any configuration of \(M\), let the table cursor be at most \(L\), and let the clock word have width \(w\) and little-endian value \(r\). Then the timed interpreter, started from the six-tape lift of the interpreter checkpoint of \(\mathrm{src}\) with that clock word, halts within
steps, and its real output is exactly the deadline-inclusive answer of \(\mathrm{src}\) at budget \(r\): halting on the final allowed transition counts as success.
The assembly of a function on five tape indices from four core values and a buffer value: indices \(0\) through \(3\) map to the core values (table, state, simulated work, and input marker) and index \(4\) to the buffer value.
The lift of a six-tape timed-interpreter action to the assembled machine with \(k + 5\) tapes, for a base machine with \(k\) tapes and a designated clock tape: the action’s clock component acts on the retained clock lane of the old block, its remaining five components act on the five fresh lanes, and all other old lanes are left untouched.
The capture wrapper of a machine \(M\) with a designated clock tape: it runs \(M\) in lockstep while writing \(M\)’s emissions to a fresh table lane instead of the output; when \(M\) halts, control transfers to the timed interpreter, which runs on the captured table, the retained clock lane, and four further fresh lanes.
The first-phase configuration of the capture wrapper corresponding to a configuration of the base machine \(M\): \(M\)’s tapes and heads are embedded, the captured-table lane holds \(M\)’s accumulated output as a buffer with head at its right blank, the remaining fresh lanes are blank, and the real output is empty.
On every input, the initial configuration of the capture wrapper equals the first-phase embedding of the base machine’s initial configuration, with a blank captured table and blank interpreter lanes.
For every live configuration of the base machine, one step of the capture wrapper from its first-phase embedding equals the embedding of one step of the base machine: the input head and the original work tapes move in lockstep, any emission — including one on the base machine’s halting transition — is appended to the captured table rather than the real output, and the later fresh lanes stay untouched; administrative states remain live.
If the base machine remains live at every time strictly below \(t\), then \(t\) steps of the capture wrapper from an embedded configuration equal the embedding of \(t\) steps of the base machine.
The interpreter-entry configuration of the capture wrapper for a halted configuration of the base machine: identical to its first-phase embedding except that the finite control is the timed interpreter’s initial state; the retained clock lane becomes active again during interpretation.
From the first-phase embedding of a halted configuration of the base machine, one step of the capture wrapper transfers control to the interpreter entry, changing no tape contents, head positions, or output.
If the base machine halts on input \(x\) within \(T\) steps, then for some \(t \le T + 1\), running the capture wrapper \(t\) steps from its initial configuration on \(x\) reaches the interpreter-entry configuration for the base machine’s configuration at time \(T\); since halting is absorbing, all fields of that configuration — including the parked input head — are retained, not merely the completed output.
The configuration of the assembled capture machine determined by a six-tape timed-interpreter configuration together with inactive tapes and heads for the old block: the interpreter’s clock lane is placed at the retained clock index of the old block, its remaining five lanes occupy the fresh indices, and every other old lane carries the given inactive data.
The six symbols read by a framed configuration on the interpreter’s active lanes (the four core lanes, the retained clock lane, and the buffer lane) coincide with the reads of the underlying six-tape interpreter configuration.
Applying the framed lift of a six-tape action to a framed configuration equals the frame of the six-tape configuration obtained by applying the action; the inactive lanes of the old block are unchanged.
One step of the assembled capture machine from a framed configuration equals the frame of one step of the timed interpreter, including the final halting transition.
For every \(t\), running the assembled capture machine \(t\) steps from a framed configuration equals the frame of the \(t\)-step timed-interpreter run, with the inactive frame unchanged.
Let a halted configuration of the base machine hold, on the designated clock tape, the buffer of a clock word with head at the word’s length. Then its interpreter-entry capture configuration equals the frame — over the base configuration’s tapes and heads — of the six-tape lift, with that clock word, of the stopped interpreter’s entry configuration on the captured table (the base configuration’s accumulated output) with the same parked input head.
The complete timed universal machine of an effective coding scheme: the capture wrapper of the composed clock-preserving canonizer, with its retained clock lane. It has finite control and finitely many tapes.
The part of the timed universal machine’s startup cost that depends only on the code string \(\alpha \): three times \(|\alpha |\), plus the canonizer’s time bound at \(|\alpha |\), plus the length of the decoded machine’s serialization, plus twice the width of its binary state count, plus twice its initial state index, plus \(16\).
For every coded machine, the header endpoint — twice the width of the binary state count, plus \(2\), plus the initial state index, plus \(1\) — is at most the length of the machine’s serialization.
On the nested pair encoding \(\langle \langle b, \alpha \rangle , x\rangle \), the timed universal machine reaches, within \(4|b|\) plus the code-only startup bound steps, a framed configuration over some inactive tapes and heads: the six-tape lift, with clock word \(b\), of the interpreter checkpoint of the decoded machine’s initial configuration on \(x\), with the table cursor just past the serialization header (at twice the binary state-count width, plus \(2\), plus the initial state index, plus \(1\)).
For all natural numbers \(S\), \(B\), \(t\), \(w\), \(s\), \(d\): if \(w \le t\), \(s \le 4w + S\), and \(d \le (B + 2w + 8)(t+1)\), then \(s + d \le (S + B + 14)(t+1)^2\).
For every effective coding scheme, code string \(\alpha \), input \(x\), and deadline \(t\), the timed universal machine on the nested pair encoding of the binary representation of \(t\), the code \(\alpha \), and the input \(x\) halts with output the deadline-inclusive answer of the decoded machine’s initial configuration at budget \(t\), within \((\text{startup bound} + \text{block bound} + 14)\, (t+1)^2\) steps, where both bounds depend only on \(\alpha \).
For every effective machine-coding scheme there is a single finite-tape machine \(U\) over \(\{ 0,1\} \) such that for every code string \(\alpha \) there is a constant \(C\) with the following two properties for every input \(x\) and every deadline \(t \in \mathbb {N}\). If the machine denoted by \(\alpha \) halts on \(x\) within \(t\) steps with output \(w\), then \(U\) on the nested pair encoding of the binary representation of \(t\), the code \(\alpha \), and the input \(x\) halts with output \(1\) followed by \(w\) within \(C (t+1)^2\) steps. If instead the denoted machine produces no output on \(x\) within \(t\) steps, then \(U\) halts with output the single timeout tag \(0\) within the same bound. Halting is checked after every simulated transition including the \(t\)-th, so halting exactly at the deadline counts as success.
175.3 Additional declarations
Let \(c\) be an effective machine-coding scheme whose canonizer runs in time \(T \colon \mathbb {N} \to \mathbb {N}\); for a bit string \(\alpha \) let \(M_\alpha \) be the machine \(\alpha \) decodes to, \(L_\alpha \) the length of its canonical serialization, \(N_\alpha \) its number of states and \(q_\alpha \) the index of its initial state, write \(\mathrm{bin}(n)\) for the binary representation of \(n\) (least significant bit first) and \(\langle a, b\rangle \) for the pair encoding of bit strings (each bit of \(a\) doubled, then \(01\), then \(b\)), and set
Then there is a single finite-tape machine \(U\) over \(\{ 0,1\} \) such that for every bit string \(\alpha \), input \(x\) and deadline \(t \in \mathbb {N}\): if \(M_\alpha \) halts on \(x\) within \(t\) steps with output \(w\), then \(U\) on \(\langle \langle \mathrm{bin}(t), \alpha \rangle , x\rangle \) halts within \(C_\alpha (t+1)^2\) steps with output \(1\) followed by \(w\); and if there is no string \(w\) such that \(M_\alpha \) halts on \(x\) within \(t\) steps with output \(w\), then \(U\) on \(\langle \langle \mathrm{bin}(t), \alpha \rangle , x\rangle \) halts within \(C_\alpha (t+1)^2\) steps with output the single bit \(0\).