160 Complexity — Encoding
160.1 Overview
This module represents Turing machines as binary strings (Arora–Barak, §1.4): it defines the code normal form (one work tape, binary alphabet, states drawn from a canonical nonempty finite type), a fixed canonical serialization of such machines, the self-delimiting pair encoding used by the universal machine together with a concrete linear-time machine computing the diagonal pairing, and the specification of a machine representation scheme — both its algebraic laws (every string decodes to a machine, and codes survive padding) and the effectivity requirement that ties decoding to computable semantics. Throughout, bit strings are written over \(\{ 0,1\} \) (\(1\) for true, \(0\) for false), and the pair encoding \(\langle x, \alpha \rangle \) of two bit strings lists each bit of \(x\) twice, then the unequal separator pair \(01\), then \(\alpha \) verbatim.
160.2 Declarations
A machine in code normal form consists of a natural number \(m\) (one less than the number of states, so the state space is never empty) together with a multi-tape Turing machine having exactly one work tape, binary tape alphabet \(\{ 0,1\} \), and state space the canonical finite type \(\{ 0, 1, \dots , m\} \).
The finite-machine bundle associated with a machine in code normal form: the binary-alphabet machine package whose number of work tapes is \(1\), whose state type is the canonical finite state space \(\{ 0,\dots ,m\} \) of the coded machine, and whose transition table is that of the coded machine.
For every machine \(M\) in code normal form, the bundled finite machine associated with \(M\) has exactly one work tape.
The self-delimiting pairing \(\langle x, \alpha \rangle \) of two bit strings: the first string \(x\) with every bit doubled, then the separator pair \(01\), then the second string \(\alpha \) verbatim. Reading aligned two-bit blocks from the left, \(00\) and \(11\) are data and the first aligned \(01\) is the separator (an aligned \(01\) can never occur inside the doubled region), so the encoding determines both components.
A partial parser on bit strings that reads aligned two-bit blocks from the left: a block \(00\) contributes the bit \(0\) and a block \(11\) contributes the bit \(1\) to the first component, and the first aligned block \(01\) is the separator, at which point the parser returns the accumulated first component together with the remaining suffix, untouched, as the second component. On strings admitting no such parse the result is undefined.
For all bit strings \(x\) and \(\alpha \), the aligned two-bit parser applied to the pair encoding \(\langle x, \alpha \rangle \) (each bit of \(x\) doubled, then the separator \(01\), then \(\alpha \) verbatim) succeeds and returns exactly the pair \((x, \alpha )\).
The map sending a pair \((x, \alpha )\) of bit strings to its pair encoding — each bit of \(x\) doubled, then the separator \(01\), then \(\alpha \) verbatim — is injective on pairs of bit strings.
A fixed six-state Turing machine over the binary alphabet with no work tapes that transforms an input \(x\) into the diagonal pair encoding \(\langle x, x\rangle \). Its six control states implement, in order: emitting the scanned bit while staying put, emitting it again while moving right, emitting the separator bit \(1\) while staying put, taking one unconditional left move, rewinding the input head to the left end, and copying the input verbatim; the first state’s blank branch emits the separator bit \(0\).
A configuration of the six-state diagonal pairing machine on an input string \(x\), specified by an optional control state among the six (absent when the machine has halted), an input-head position in \(\{ 0, \dots , |x| + 1\} \), and the output string emitted so far. The machine has no work tapes, so the work-tape components of the configuration are vacuous.
Consider the six-state diagonal pairing machine on an input string \(x\), in a live configuration with control state \(q\), input-head position \(p\), and output string \(w\), and suppose the symbol scanned by the input head is \(b\) (a bit or the blank). Then one step of the machine yields exactly the configuration prescribed by the transition table entry at \((q, b)\): its successor state (or halting), the head position \(p\) moved by the prescribed direction, and the output \(w\) extended by the emitted bit, if any.
For the six-state diagonal pairing machine on an input string \(x\), in any configuration whose input head sits at position \(j + 1\) with \(j \lt |x|\), the scanned input symbol is the \(j\)-th bit of \(x\), for every control state and every output string.
For the six-state diagonal pairing machine on an input string \(x\), in any configuration whose input head sits at the right boundary position \(|x| + 1\), the scanned input symbol is the blank, for every control state and every output string — including on the empty input.
Let \(x\) be a bit string and \(t \le |x|\). Running the six-state diagonal pairing machine from its initial configuration on input \(x\) for exactly \(2t\) steps yields the configuration in the initial control state with input head at position \(t + 1\) whose output is the first \(t\) bits of \(x\) with each bit doubled.
Let \(x\) be a bit string, \(w\) an output string, and \(j \le |x|\). Running the six-state diagonal pairing machine for exactly \(j + 1\) steps from the configuration in its rewind state (state \(4\)) with input head at position \(j\) and output \(w\) yields the configuration in its copy state (state \(5\)) with input head at position \(1\) and output still \(w\).
Let \(x\) be a bit string, \(w\) an output string, and \(t \le |x|\). Running the six-state diagonal pairing machine for exactly \(t\) steps from the configuration in its copy state (state \(5\)) with input head at position \(1\) and output \(w\) yields the configuration still in the copy state with input head at position \(t + 1\) and output \(w\) followed by the first \(t\) bits of \(x\).
Let \(x\) be a bit string and \(w\) an output string. Running the six-state diagonal pairing machine for exactly \(3\) steps from the configuration in its initial control state with input head at the right boundary position \(|x| + 1\) and output \(w\) yields the configuration in its rewind state (state \(4\)) with input head at position \(|x|\) and output \(w\) followed by the separator pair \(01\).
For every bit string \(x\) of length \(n\), running the six-state diagonal pairing machine from its initial configuration on input \(x\) for exactly \(4n + 5\) steps yields a halted configuration with input head at position \(n + 1\) whose output is the diagonal pair encoding \(\langle x, x\rangle \) (each bit of \(x\) doubled, then the separator \(01\), then \(x\) verbatim).
There exist a finite-state machine \(M\) over the binary alphabet and a constant \(c\) such that on every input string \(\alpha \) of length \(n\), the machine \(M\) halts within \(c \cdot (n + 1)\) steps with output the diagonal pair encoding \(\langle \alpha , \alpha \rangle \) (each bit of \(\alpha \) doubled, then the separator \(01\), then \(\alpha \) verbatim). In particular the diagonal pairing \(\alpha \mapsto \langle \alpha , \alpha \rangle \) is computable in linear time.
The fixed two-bit serialization of a head move: a left move is \(11\), staying put is \(00\), and a right move is \(10\).
The fixed two-bit serialization of an optional bit: absent is \(00\), the bit \(0\) is \(10\), and the bit \(1\) is \(11\).
The fixed two-bit serialization of an optional write action on a binary tape, where a present write may itself write the blank: no write is \(00\), writing the blank is \(01\), writing the bit \(0\) is \(10\), and writing the bit \(1\) is \(11\).
The self-delimiting unary serialization of an index \(s \in \{ 0,\dots ,n-1\} \): \(s\) copies of the bit \(1\) followed by a single bit \(0\).
The serialization of an optional successor state: halting (no successor) is the single bit \(0\), and a successor state \(s\) is the bit \(1\) followed by the self-delimiting unary serialization of \(s\).
The serialization of a single transition record of a one-work-tape binary machine with \(n + 1\) states: the concatenation of the two-bit input-head move, the two-bit optional write on the work tape, the two-bit work-head move, the two-bit optional output emission, and the self-delimiting serialization of the optional successor state.
The fixed, scheme-independent canonical serialization of a machine in code normal form: the pair encoding whose first component is the binary representation of the state-count parameter (self-delimiting via the doubled-bit region) and whose second component is the self-delimiting unary serialization of the initial state followed by the serialized transition records of the entire transition table, listed in a fixed enumeration order (states in increasing order, with the scanned input symbol and the scanned work symbol each ranging over blank, \(0\), \(1\)).
The algebraic laws of a representation scheme for machines in code normal form: an encoding map from coded machines to bit strings, a total decoding map from bit strings to coded machines (so every string represents some machine), and the law that the code of a machine followed by any number of padding bits \(1\) decodes back to that machine (so every machine has infinitely many representations).
For every representation scheme satisfying the algebraic laws and every machine \(M\) in code normal form, decoding the code of \(M\) yields \(M\) itself.
An effective representation scheme: a representation scheme satisfying the algebraic laws, together with a canonizer — a finite-state binary-alphabet machine — and a time bound \(T : \mathbb {N} \to \mathbb {N}\) such that on every bit string \(\alpha \) the canonizer halts within \(T(|\alpha |)\) steps and outputs the fixed canonical serialization of the machine to which \(\alpha \) decodes.
Let \(M\) be a machine over the binary alphabet with finitely many states and exactly one work tape. Then there exists a machine \(M'\) in code normal form such that for every input string \(x\), every output string \(w\), and every time bound \(t\), the bundled machine of \(M'\) halts on \(x\) within \(t\) steps with output \(w\) if and only if \(M\) does.
160.3 Additional declarations
For a bit string \(w = w_0 w_1 \cdots w_{n-1}\), its doubling \(\mathrm{dbl}(w)\) is the bit string \(w_0 w_0 w_1 w_1 \cdots w_{n-1} w_{n-1}\) obtained by writing every bit of \(w\) twice in succession.
The doubling of the empty bit string (the string obtained by writing each of its bits twice in succession) is the empty bit string.
For every bit \(b\) and every bit string \(w\), the doubling of the string \(b\, w\) (where \(\mathrm{dbl}(v)\) writes each bit of \(v\) twice in succession) is \(b\, b\) followed by \(\mathrm{dbl}(w)\); that is, \(\mathrm{dbl}(b\, w) = b\, b\, \mathrm{dbl}(w)\).
For every bit string \(w\), its doubling \(\mathrm{dbl}(w)\), obtained by writing each bit of \(w\) twice in succession, has length \(\left\lvert \mathrm{dbl}(w)\right\rvert = 2\left\lvert w\right\rvert \).
Let \(w = w_0 w_1 \cdots w_{n-1}\) be a bit string, let \(c \lt n\), and let \(p \in \{ 0, 1\} \). Then the doubling \(\mathrm{dbl}(w)\) (each bit of \(w\) written twice in succession, positions indexed from \(0\)) has a symbol at position \(2c + p\), and that symbol is \(w_c\).
For all bit strings \(x\) and \(y\), the self-delimiting pair encoding \(\langle x, y\rangle \) equals the concatenation
where \(\mathrm{dbl}(x)\) is \(x\) with every bit written twice in succession, followed by the separator bits \(0\) then \(1\), followed by \(y\) verbatim.
For all bit strings \(x\) and \(y\), the pair encoding \(\langle x, y\rangle \) (each bit of \(x\) written twice, then the separator bits \(0\) then \(1\), then \(y\) verbatim) has length \(\left\lvert \langle x, y\rangle \right\rvert = 2\left\lvert x\right\rvert + 2 + \left\lvert y\right\rvert \).
Consider the aligned pair parser on bit strings, which reads aligned two-bit blocks from the left, treats the blocks \(00\) and \(11\) as data bits \(0\) and \(1\), and stops successfully at the first aligned block \(01\). If the parser fails on a bit string \(z\), then \(z = \mathrm{dbl}(w)\, \tau \) for some bit string \(w\) (with \(\mathrm{dbl}(w)\) denoting \(w\) with every bit written twice) and some tail \(\tau \) that is either empty, a single bit, or begins with the bits \(1\) then \(0\).
Let \(z\), \(a\), \(b\) be bit strings, and consider the aligned pair parser, which reads aligned two-bit blocks from the left, collects the data bits \(0\) and \(1\) from the blocks \(00\) and \(11\), and at the first aligned block \(01\) returns the collected bits together with the remaining suffix. If the parser succeeds on \(z\) and returns \((a, b)\), then \(z\) is the pair encoding \(\langle a, b\rangle \), i.e. \(a\) with every bit written twice, then the separator bits \(0\) then \(1\), then \(b\) verbatim.
Let \(n, n' \in \mathbb {N}\) and let \(u, u'\) be bit strings. Write \(\langle x, y\rangle \) for the pair encoding of bit strings \(x\) and \(y\) (each bit of \(x\) written twice, then the separator bits \(0\) then \(1\), then \(y\) verbatim). If \(\langle 1^n, u\rangle = \langle 1^{n'}, u'\rangle \), where \(1^n\) denotes the string of \(n\) ones, then \(n = n'\) and \(u = u'\).
For every natural number \(m\), the binary expansion of \(m\) without leading zeros (where \(0\) has the empty expansion) consists of at most \(m\) bits.