176 Complexity — Universal Block
176.1 Overview
This module completes the live serialized-table block of the universal Turing machine (Arora–Barak, §1.4.1, Theorem 1.9): exact-cost skipping and selection of transition records over the canonical serialized table, reading of the eight fixed action bits, successor decoding and installation, and the application of the decoded record, assembled into the block lemma that one live step of the simulated machine is realized by the fixed four-tape table interpreter within a code-dependent budget. It also provides the concrete checkpoint relation between source and universal-machine configurations, its startup, halting, and output correspondence lemmas, and the block budget itself. Throughout, bit strings are written over \(\{ 0,1\} \) (\(1\) for true, \(0\) for false), \(1^n\) denotes \(n\) consecutive \(1\)s, and “the table is \(w\)” means that the interpreter’s first work tape is the two-way infinite tape holding the bit string \(w\) in cells \(0, \dots , |w| - 1\) with blanks elsewhere, its cursor position counted from cell \(0\).
176.2 Declarations
Suppose the table is \(l \cdot 1^n \cdot 0 \cdot r\). From the table interpreter’s unary-skipping phase, carrying a destination and a count of remaining records in \(\{ 0, \dots , 8\} \), with table cursor \(|l|\), exactly \(n + 1\) interpreter steps advance the cursor to \(|l| + n + 1\) and pass control to the continuation after a skip request for the destination when the remaining count is \(0\), and to the fixed-field skipping phase with the count decremented and a cleared field register otherwise; the state tape, state cursor, and all other data are unchanged.
Suppose the table is \(l \cdot \rho \cdot r\), where \(\rho \) is the serialized transition record of a one-work-tape machine action over \(\{ 0,1\} \) (its eight fixed action bits followed by its self-delimiting unary successor field). From the interpreter’s fixed-field skipping phase, carrying a destination and a count of remaining records in \(\{ 0, \dots , 8\} \), with field register \(0\) and table cursor \(|l|\), exactly \(|\rho |\) interpreter steps advance the cursor to \(|l| + |\rho |\) and pass control to the continuation after a skip request for the destination when the remaining count is \(0\), and to the fixed-field skipping phase with the count decremented and a cleared field register otherwise; the state tape, state cursor, and all other data are unchanged.
Let \(a_1, \dots , a_{m+1}\) be one-work-tape machine actions over \(\{ 0,1\} \) whose serialized transition records appear consecutively in the table after a prefix \(l\), and consider the interpreter’s fixed-field skipping phase carrying a destination and the remaining-record count \(m \in \{ 0, \dots , 8\} \), with field register \(0\) and table cursor \(|l|\). Then exactly as many interpreter steps as the total length of the \(m + 1\) serialized records advance the table cursor past all of them and enter the continuation after a skip request for the destination; the state tape, state cursor, and all other data are unchanged.
Suppose the table is \(l \cdot G \cdot r\), where \(G\) concatenates the serialized transition records of \(g\) groups of one-work-tape machine actions, each group containing exactly nine records, and suppose the state tape is the state window with \(j\) erased and \(g\) remaining unary cells, with state cursor \(j + 1\). From the interpreter’s record-group phase carrying a read index \(i \in \{ 0, \dots , 8\} \), with table cursor \(|l|\), exactly \(g + |G| + 1\) interpreter steps reach the state-rewind phase remembering \(i\), with table cursor \(|l| + |G|\), state tape the state window with \(j + g\) erased and no remaining unary cells, and state cursor \(j + g + 1\): each remaining unary state symbol is erased at the cost of one step plus a nine-record skip, and the terminating blank costs one further step.
Suppose the table is \(l \cdot b_0 b_1 \cdots b_7 \cdot r\) for bits \(b_0, \dots , b_7\). Consider the interpreter’s action-reading phase at a field \(f \in \{ 0, \dots , 7\} \), with table cursor \(|l| + f\) and a bit register agreeing with \(b\) at every index below \(f\). Then exactly \(8 - f\) interpreter steps reach the successor-decoding phase carrying the complete register \(b_0, \dots , b_7\), with table cursor \(|l| + 8\); the state tape, state cursor, and all other data are unchanged.
The number of interpreter steps needed to decode the successor field of a serialized record and install the successor state in unary, before the decoded action is applied: \(1\) when there is no successor state (the action halts), and \(2q + 4\) when the successor state has index \(q\).
Suppose the table is \(l \cdot 1^u \cdot 0 \cdot r\), where \(u\) is the unary size of an optional successor state (\(0\) when the successor is absent and \(q + 1\) when it has index \(q\)). From the interpreter’s successor-decoding phase carrying eight buffered action bits, with table cursor \(|l|\), state tape the intact unary encoding of the index \(0\), and state cursor \(1\), exactly the successor-preparation cost (\(1\) when the successor is absent and \(2q + 4\) otherwise) in interpreter steps reaches the record-application phase carrying the same bits and a flag recording whether the successor is absent, with table cursor \(|l| + u\), state tape the intact unary encoding of the successor index (\(0\) when absent), and state cursor \(1\).
For a coded machine \(M\) and a state \(q\) of \(M\), the list of the nine transition actions of \(q\): for each input read and each work read, ranging over blank, \(0\), \(1\) in the fixed serialization order with the input read varying slowest, the action \(M\) performs at \(q\) on that read pair.
For every coded machine \(M\), state \(q\) of \(M\), and pair of reads (an input symbol and a work symbol, each blank, \(0\), or \(1\)): the list of the nine actions of \(q\) has length \(9\), and its entry at the record index of the read pair (three times the serialization index of the input read plus the serialization index of the work read) is exactly the action \(M\) performs at \(q\) on those reads.
The header of the canonical serialization of a coded machine \(M\) with state count \(m\) and initial state index \(q_0\): the pair encoding of the binary digit string of \(m\) with the empty string (each digit doubled, then the unequal delimiter pair), followed by \(1^{q_0} \cdot 0\), the initial state in unary with its terminator. It comprises everything preceding the transition records.
The canonical serialization of a coded machine \(M\) equals its header followed by the concatenation, over every state of \(M\) in increasing order, of the concatenated serialized transition records of that state’s nine-action list (its actions on all read pairs, in the fixed input-major serialization order).
For every coded machine \(M\), state \(q\) of \(M\), and pair of reads (an input symbol and a work symbol, each blank, \(0\), or \(1\)), the canonical serialization of \(M\) decomposes as: the header, then the concatenated serialized records of a list of exactly \(q\) groups of nine actions each (the full groups of the states preceding \(q\)), then the concatenated serialized records of a list of actions whose length is the record index of the read pair, then the serialized record of the action \(M\) performs at \(q\) on those reads, then a remainder.
For every one-work-tape machine action \(a\) over \(\{ 0,1\} \), the eight fixed bits of its serialized record decode back to its components: bits \(0, 1\) decode to \(a\)’s input-head movement, bits \(2, 3\) to its optional work-tape write, bits \(4, 5\) to its work-head movement, and bits \(6, 7\) to its optional output emission (bit \(6\) flags whether an output is emitted and bit \(7\) is the emitted bit).
Let \(M\) be a coded machine, \(\alpha \) a code string, \(s\) a configuration of \(M\)’s one-work-tape form on an input \(x\), and \(a\) a transition action of \(M\). One step of the table interpreter from the evaluation configuration over the interpreter checkpoint of \(s\) (at an arbitrary table cursor) whose control is the record-application phase carrying the eight fixed bits of \(a\) and the flag recording whether \(a\) halts, whose table is the canonical serialization of \(M\) at a cursor \(p\), and whose state tape is the intact unary encoding of \(a\)’s successor index (\(0\) when \(a\) halts) with state cursor \(1\), is exactly the interpreter checkpoint of the configuration obtained by applying \(a\) to \(s\), with table cursor \(p\).
Suppose the table is \(l \cdot G \cdot B \cdot r\), where \(G\) concatenates the serialized transition records of \(g\) groups of nine one-work-tape machine actions each and \(B\) concatenates the serialized records of a list of actions whose length is a read index \(i \in \{ 0, \dots , 8\} \), and suppose the state tape is the intact unary encoding of \(g\) with state cursor \(1\). From the interpreter’s record-group phase carrying \(i\), with table cursor \(|l|\), exactly \(2g + |G| + |B| + 3\) interpreter steps reach the action-reading phase at field \(0\) with a cleared bit register, table cursor \(|l| + |G| + |B|\), state tape the intact unary encoding of \(0\), and state cursor \(1\): the two table scans cost their serialized lengths, and the destructive state count with its rewind costs \(2g + 3\).
For a multi-tape machine over \(\{ 0,1\} \) and configurations \(a\), \(b\), \(c\) on a common input: if running the machine for \(s\) steps from \(a\) yields \(b\), and running it for \(t\) steps from \(b\) yields \(c\), then running it for \(s + t\) steps from \(a\) yields \(c\).
Let \(M\) be a coded machine with state count \(N\) and canonical serialization of length \(L\), let \(\alpha \) be a code string, let \(s\) be a configuration of \(M\)’s one-work-tape form on an input \(x\) that has not halted, and let \(p \le L\) be a table cursor. Then there exist a duration \(d\) with \(1 \le d \le 3L + 5(N + 1) + 20\) and a cursor \(p' \le L\) such that running the table interpreter for \(d\) steps from the interpreter checkpoint of \(s\) with table cursor \(p\) yields exactly the interpreter checkpoint of the configuration obtained from \(s\) by one step of \(M\), with table cursor \(p'\).
The code-dependent block budget of the universal machine for an effective machine-coding scheme on a code string \(\alpha \):
where \(L\) is the length of the canonical serialization of the machine decoded from \(\alpha \) and \(N\) is that machine’s state count.
For an effective machine-coding scheme \(c\), a code string \(\alpha \), and an input \(x\): the relation between a configuration \(s\) of the machine decoded from \(\alpha \) (in one-work-tape form) on \(x\) and a configuration \(t\) of the complete universal-machine candidate on the pair encoding \(\langle \alpha , x \rangle \) that holds when there exist a table cursor \(p\) not exceeding the length of the canonical serialization of the decoded machine, together with contents and head positions for the inactive canonizer tapes, such that \(t\) is the right-block embedding, over those inactive tapes, of the interpreter checkpoint of \(s\) with table cursor \(p\).
For every coded machine \(M\) with state count \(m\) and initial state index \(q_0\): writing \(\ell \) for the number of binary digits of \(m\) and \(L\) for the length of the canonical serialization of \(M\), one has \(2\ell + 2 + q_0 + 1 \le L\); that is, the position just past the doubled count field, its delimiter pair, and the unary initial-state field with its terminator lies within the serialized table.
For every effective machine-coding scheme \(c\), code string \(\alpha \), and input \(x\), there is a time \(t\) not exceeding the startup bound for \(\alpha \) such that the concrete checkpoint relation holds between the initial configuration of the machine decoded from \(\alpha \) on \(x\) and the configuration of the complete universal-machine candidate after \(t\) steps from its initial configuration on the pair encoding \(\langle \alpha , x \rangle \).
Let \(c\) be an effective machine-coding scheme, \(\alpha \) a code string, and \(x\) an input. If the concrete checkpoint relation holds between a configuration \(s\) of the machine decoded from \(\alpha \) on \(x\) and a configuration \(t\) of the complete universal-machine candidate on the pair encoding \(\langle \alpha , x \rangle \), then \(s\) has halted if and only if \(t\) has halted.
Let \(c\) be an effective machine-coding scheme, \(\alpha \) a code string, and \(x\) an input. If the concrete checkpoint relation holds between a configuration \(s\) of the machine decoded from \(\alpha \) on \(x\) and a configuration \(t\) of the complete universal-machine candidate on the pair encoding \(\langle \alpha , x \rangle \), then the accumulated output of \(s\) equals the accumulated output of \(t\).