164 Complexity — Alphabet Reduction
164.1 Overview
This module proves the in-model analogue of [AB09, Claim 1.5]: a Turing machine over any finite alphabet \(\Gamma \) (with a read-only input tape, a write-only output tape, and \(k\) work tapes) that computes a binary string function via a bit embedding \(e : \{ 0,1\} \hookrightarrow \Gamma \) within time \(T\) is simulated by a machine over the binary alphabet with the same number of work tapes within time \(c \cdot (T(n)+1)\) for a constant \(c\) depending only on \(\left\lvert \Gamma \right\rvert \). Each work-tape symbol is stored as a fixed-width block of \(N+1\) optional bits via an injective code (the implementation uses a one-hot code of width \(\left\lvert \Gamma \right\rvert +1\), with logical blank coded by the all-blank block); one source step is simulated by a rightward read sweep, a dispatch transition, a leftward write sweep, and a whole-block head move, for exactly \(3(N+1)+2\) simulator steps per source step.
164.2 Declarations
For \(N \in \mathbb {N}\), a block is a vector of \(N+1\) cells indexed by \(\{ 0,\dots ,N\} \), each cell holding either a bit or the blank. Blocks serve as the fixed-width binary encodings of single work-tape symbols.
For \(N \in \mathbb {N}\) and an integer tape position \(p \in \mathbb {Z}\), the index \(\lfloor p/(N+1) \rfloor \) of the length-\((N+1)\) block of cells containing \(p\).
For \(N \in \mathbb {N}\) and \(p \in \mathbb {Z}\), the nonnegative remainder \(p \bmod (N+1)\), viewed as an element of \(\{ 0,\dots ,N\} \): the offset of position \(p\) inside the length-\((N+1)\) block containing it.
For \(N \in \mathbb {N}\), a block index \(z \in \mathbb {Z}\), and an offset \(j \in \mathbb {N}\), the integer tape position \((N+1)z + j\) of the \(j\)-th cell of the \(z\)-th length-\((N+1)\) block.
For every \(N \in \mathbb {N}\), every \(z \in \mathbb {Z}\), and every \(j \in \{ 0,\dots ,N\} \), the position \(p = (N+1)z + j\) satisfies \(\lfloor p/(N+1) \rfloor = z\) and \(p \bmod (N+1) = j\).
For every \(N \in \mathbb {N}\) and every \(p \in \mathbb {Z}\),
For \(N \in \mathbb {N}\), \(z, z' \in \mathbb {Z}\), and \(j, j' \in \{ 0,\dots ,N\} \), one has \((N+1)z + j = (N+1)z' + j'\) if and only if \(z = z'\) and \(j = j'\).
Given \(N \in \mathbb {N}\) and a family \(F\) assigning to every integer \(z\) a block of \(N+1\) optional bits, the induced binary tape \(\mathbb {Z} \to \{ 0,1\} \cup \{ \text{blank}\} \): position \(p\) holds entry \(p \bmod (N+1)\) of the block \(F(\lfloor p/(N+1) \rfloor )\).
Let \(F\) assign to every integer a block of \(N+1\) optional bits. The binary tape induced by \(F\) (position \(p\) holding entry \(p \bmod (N+1)\) of block \(F(\lfloor p/(N+1)\rfloor )\)) reads, at position \((N+1)z + j\) with \(z \in \mathbb {Z}\) and \(j \in \{ 0,\dots ,N\} \), exactly the entry \(j\) of \(F(z)\).
Fix \(N \in \mathbb {N}\). Two binary tapes \(u, v : \mathbb {Z} \to \{ 0,1\} \cup \{ \text{blank}\} \) that agree at every position of the form \((N+1)z + j\) with \(z \in \mathbb {Z}\) and \(j \in \{ 0,\dots ,N\} \) are equal.
Let \(F\) assign to every integer a block of \(N+1\) optional bits, let \(z \in \mathbb {Z}\), \(j \in \{ 0,\dots ,N\} \), and let \(b\) be an optional bit. Overwriting the binary tape induced by \(F\) at position \((N+1)z + j\) with the value \(b\) yields the binary tape induced by the family that agrees with \(F\) everywhere except that entry \(j\) of block \(z\) becomes \(b\).
For a finite alphabet \(\Gamma \), an injection of \(\Gamma \cup \{ \text{blank}\} \) into blocks of \(\left\lvert \Gamma \right\rvert +1\) optional bits: the blank maps to the all-blank block, and a symbol \(x \in \Gamma \) maps to the block whose entry at offset \(j\) is the genuine bit that is \(1\) exactly when \(j\) is the index of \(x\) under a fixed enumeration of \(\Gamma \).
Given an injection \(E\) of \(\Gamma \cup \{ \text{blank}\} \) into blocks of \(N+1\) optional bits, a total decoding map from blocks to \(\Gamma \cup \{ \text{blank}\} \) chosen as a left inverse of \(E\): every block in the image of \(E\) is sent to its unique preimage.
Let \(E\) be an injection of \(\Gamma \cup \{ \text{blank}\} \) into blocks of \(N+1\) optional bits, and let the decoder be the associated left inverse of \(E\). Then for every \(a \in \Gamma \cup \{ \text{blank}\} \), decoding the block \(E(a)\) returns \(a\).
For an embedding \(e : \{ 0,1\} \hookrightarrow \Gamma \) of the two bits into an alphabet \(\Gamma \) and a symbol \(a \in \Gamma \), the bit that is \(1\) exactly when \(a = e(1)\); in particular every symbol outside the image of \(e\) decodes to \(0\).
Let \(e : \{ 0,1\} \hookrightarrow \Gamma \) be an embedding of the bits into an alphabet \(\Gamma \). For every bit \(b\), applying the total bit decoder (which sends \(a \in \Gamma \) to \(1\) exactly when \(a = e(1)\)) to \(e(b)\) returns \(b\).
For an alphabet \(\Gamma \), a state type \(S\), and \(k \in \mathbb {N}\) work tapes, a pending record consists of an optional next state (absence meaning halt), for each of the \(k\) work tapes an element of \(\Gamma \cup \{ \text{blank}\} \) to be written, and for each work tape a head movement direction in \(\{ -1,0,+1\} \).
The finite state space of the block-code simulator with parameters \(\Gamma \), \(S\), \(k\), \(N\): either a reading state, consisting of a source state \(q \in S\), a counter \(j \in \{ 0,\dots ,N+1\} \), and for each of the \(k\) work tapes a partially filled buffer block of \(N+1\) optional bits; or a pending record (optional next state, per-tape symbol to write, per-tape direction) together with either a write counter in \(\{ 0,\dots ,N\} \) or a move counter in \(\{ 0,\dots ,N+1\} \).
For a source state \(q\), the simulator state at a macro-step boundary: the reading state with source state \(q\), counter \(0\), and all-blank buffer blocks.
Given the vector of symbols currently scanned under the \(k\) work heads and a source machine action \(a\) (next state, per-tape optional write and head move, input-head move, optional emission), the pending record retaining: the next state of \(a\); for each work tape the effective new symbol (the symbol \(a\) writes, or the scanned symbol when \(a\) writes nothing); and the head movement direction of \(a\) on each work tape.
Given a finite alphabet \(\Gamma \), an injective block code \(E\) of \(\Gamma \cup \{ \text{blank}\} \) into blocks of \(N+1\) optional bits, a bit embedding \(e : \{ 0,1\} \hookrightarrow \Gamma \), and a Turing machine \(M\) over \(\Gamma \) (read-only input tape, write-only output tape, \(k\) work tapes), the simulating machine over the binary alphabet with the same number \(k\) of work tapes. Its control cycles through: \(N+1\) reading steps that copy the block under each work head into a buffer while moving right; one dispatch step that decodes the buffers, applies the transition of \(M\) (with the scanned input bit mapped through \(e\)), performs the input-head move of \(M\), emits the bit-decoded image of any emitted symbol, stores the resulting pending record, and moves each work head one cell left; \(N+1\) writing steps that write the coded new symbols right to left; and \(N+2\) moving steps that shift each work head one whole block in its source direction and then re-enter the reading state (halting if the source transition halts).
Let \(E\) be an injective block code of \(\Gamma \cup \{ \text{blank}\} \) into blocks of \(N+1\) optional bits, \(e : \{ 0,1\} \hookrightarrow \Gamma \) a bit embedding, \(x\) a binary string, and \(c\) a configuration of a \(\Gamma \)-machine with \(k\) work tapes on the letterwise \(e\)-image of \(x\). The encoded simulator configuration on the genuine binary input \(x\): its state is the initial reading state for the state of \(c\) (halted when \(c\) is halted); the input-head position is unchanged; work tape \(i\) is the binary tape induced by coding the corresponding tape of \(c\) blockwise through \(E\); work head \(i\) sits at offset \(0\) of the block of its source head position; and the output of \(c\) is decoded bitwise (a symbol \(a\) becoming \(1\) exactly when \(a = e(1)\)).
Let \(e : \{ 0,1\} \hookrightarrow \Gamma \) be a bit embedding, \(x\) a binary string, and \(c\) a configuration of a \(\Gamma \)-machine on the letterwise \(e\)-image of \(x\). The input symbol scanned by the encoded simulator configuration of \(c\) (which reads the genuine binary input \(x\) at the same input-head position), mapped through \(e\), equals the input symbol scanned by \(c\); in particular both are absent for the same head positions.
Given an injective block code \(E\) of \(\Gamma \cup \{ \text{blank}\} \) into blocks of \(N+1\) optional bits, a vector assigning to each of \(k\) work tapes a scanned element of \(\Gamma \cup \{ \text{blank}\} \), and a count \(j \in \mathbb {N}\): the per-tape buffer after \(j\) reading steps, namely for each tape \(i\) the block whose entries at offsets \(\lt j\) agree with the code of the scanned symbol of tape \(i\) and whose remaining entries are blank.
After zero reading steps the per-tape buffer (entries at offsets below the count taken from the coded scanned symbols, blank elsewhere) is the all-blank block on every tape.
After \(N+1\) reading steps the per-tape buffer holds, on each tape \(i\), the complete code of the symbol scanned on tape \(i\).
For \(j \in \{ 0,\dots ,N\} \), overwriting entry \(j\) of the \(j\)-step buffer of each tape with entry \(j\) of the code of that tape’s scanned symbol yields the \((j+1)\)-step buffer.
The simulator configuration \(j\) steps into the read sweep of a macro step, for a source configuration \(c\), a source state \(q\), and \(j \in \{ 0,\dots ,N+1\} \): it agrees with the encoded configuration of \(c\) except that its state is the reading state with source state \(q\), counter \(j\), and the \(j\)-step buffers of the symbols scanned by \(c\), and each work head sits at offset \(j\) of the block of its source head position.
If the source configuration \(c\) is in state \(q\) (in particular not halted), then the read-sweep configuration of \(c\) at counter \(0\) coincides with the encoded configuration of \(c\).
For a counter \(j \le N\), the work-tape symbols scanned by the read-sweep configuration of a source configuration \(c\) at counter \(j\) are, on each tape \(i\), the entry at offset \(j\) of the code of the symbol scanned by \(c\) on tape \(i\).
For a counter \(j \le N\), one transition of the binary block-code simulator applied to the read-sweep configuration of a source configuration \(c\) with source state \(q\) at counter \(j\) yields the read-sweep configuration at counter \(j+1\): the scanned code bits enter the buffers and every work head moves one cell right.
Let \(c\) be a source configuration in state \(q\) (not halted). For every \(j \le N+1\), running the binary block-code simulator for \(j\) steps from the encoded configuration of \(c\) reaches the read-sweep configuration of \(c\) at counter \(j\).
Given an injective block code \(E\) of \(\Gamma \cup \{ \text{blank}\} \) into blocks of \(N+1\) optional bits, a source tape \(t : \mathbb {Z} \to \Gamma \cup \{ \text{blank}\} \), a position \(p \in \mathbb {Z}\), a symbol \(w\) to be written at \(p\), and a counter \(r \in \mathbb {N}\): the family of blocks coding the partially rewritten tape, where every block \(z \neq p\) is the code of \(t(z)\), and block \(p\) takes its entries at offsets \(\ge r\) from the code of \(w\) and its entries at offsets \(\lt r\) from the code of \(t(p)\).
At counter \(N+1\) (before anything is written) the partially rewritten block family for tape \(t\), write position \(p\), and new symbol \(w\) is simply the blockwise coding \(z \mapsto E(t(z))\) of the unmodified tape.
At counter \(0\) (after the write is complete) the partially rewritten block family for tape \(t\), write position \(p\), and new symbol \(w\) is the blockwise coding of the updated tape that agrees with \(t\) everywhere except that position \(p\) now holds \(w\).
For \(j \in \{ 0,\dots ,N\} \), overwriting the binary tape induced by the counter-\((j+1)\) partially rewritten block family (tape \(t\), write position \(p\), new symbol \(w\)) at tape position \((N+1)p + j\) with entry \(j\) of the code of \(w\) yields the binary tape induced by the counter-\(j\) family: blocks other than \(p\) are unchanged, and within block \(p\) the only new entry is the one at offset \(j\).
The simulator configuration in the move sweep at counter \(r \in \{ 0,\dots ,N+1\} \), for a source configuration \(c\) and a source action \(a\): the work tapes, input position, and output are those of the encoded configuration of the result of applying \(a\) to \(c\); the state carries the pending record of \(a\) with move counter \(r\); and work head \(i\) sits at position \((N+1)p_i + (N+1-r)\, d_i\), where \(p_i\) is the source head position of \(c\) on tape \(i\) and \(d_i \in \{ -1,0,+1\} \) is the movement of \(a\) on tape \(i\).
The simulator configuration in the write sweep at counter \(j \in \{ 0,\dots ,N\} \), for a source configuration \(c\) and a source action \(a\): the state carries the pending record of \(a\) with write counter \(j\); work tape \(i\) is the binary tape induced by the partially rewritten block family in which, at the block of the source head position, the entries at offsets \(\gt j\) already hold the code of the effective new symbol (the symbol \(a\) writes, or the currently scanned symbol when \(a\) writes nothing); work head \(i\) sits at offset \(j\) of that block; and the input position and output are those of the encoded configuration of the result of applying \(a\) to \(c\).
For a counter \(r \neq 0\), one transition of the binary block-code simulator applied to the move-sweep configuration (source configuration \(c\), source action \(a\)) at counter \(r\) yields the move-sweep configuration at counter \(r-1\): each work head advances one cell in its pending direction.
One transition of the binary block-code simulator applied to the move-sweep configuration (source configuration \(c\), source action \(a\)) at counter \(0\) yields the encoded configuration of the result of applying \(a\) to \(c\); in particular the simulator halts exactly when the next state of \(a\) is absent.
For every counter \(r \le N+1\), running the binary block-code simulator for \(r+1\) steps from the move-sweep configuration (source configuration \(c\), source action \(a\)) at counter \(r\) reaches the encoded configuration of the result of applying \(a\) to \(c\).
For a counter \(j \neq 0\), one transition of the binary block-code simulator applied to the write-sweep configuration (source configuration \(c\), source action \(a\)) at counter \(j\) yields the write-sweep configuration at counter \(j-1\): on each tape the entry at offset \(j\) of the code of the effective new symbol is written and the head moves one cell left.
One transition of the binary block-code simulator applied to the write-sweep configuration (source configuration \(c\), source action \(a\)) at counter \(0\) writes the last code entry in place and yields the move-sweep configuration at counter \(N+1\): the work tapes now hold the complete blockwise coding of the tapes of the result of applying \(a\) to \(c\).
For every counter \(j \le N\), running the binary block-code simulator for \(j+1\) steps from the write-sweep configuration (source configuration \(c\), source action \(a\)) at counter \(j\) reaches the move-sweep configuration at counter \(N+1\).
Let \(M\) be a Turing machine over a finite alphabet \(\Gamma \), \(c\) a configuration of \(M\) on the letterwise \(e\)-image of a binary string, and \(q\) a source state. One transition of the binary block-code simulator applied to the read-sweep configuration of \(c\) at the full counter \(N+1\) (all blocks buffered) yields the write-sweep configuration at counter \(N\) for the action produced by the transition function of \(M\) on the state \(q\), the input symbol scanned by \(c\), and the work-tape symbols scanned by \(c\): the buffers are decoded, the input head moves and any emission is bit-decoded and emitted, and each work head steps left onto the last entry of its block.
Let \(M\) be a Turing machine over a finite alphabet \(\Gamma \) and \(c\) a configuration of \(M\) on the letterwise \(e\)-image of a binary string. Running the binary block-code simulator for \(3(N+1)+2\) steps from the encoded configuration of \(c\) yields the encoded configuration of the result of one step of \(M\) from \(c\); when \(c\) is halted both encoded configurations are fixed points, so the identity holds in that case as well.
Let \(M\) be a Turing machine over a finite alphabet \(\Gamma \) and \(c\) a configuration of \(M\) on the letterwise \(e\)-image of a binary string. For every \(t \in \mathbb {N}\), running the binary block-code simulator for \((3(N+1)+2)\cdot t\) steps from the encoded configuration of \(c\) yields the encoded configuration of the configuration reached by \(M\) after \(t\) steps from \(c\).
Suppose the injective block code \(E\) sends the blank to the all-blank block. Then for every Turing machine \(M\) over a finite alphabet \(\Gamma \), every bit embedding \(e : \{ 0,1\} \hookrightarrow \Gamma \), and every binary string \(x\), the initial configuration of the binary block-code simulator on input \(x\) equals the encoded initial configuration of \(M\) on the letterwise \(e\)-image of \(x\).
Let \(M\) be a Turing machine over an alphabet \(\Gamma \) and \(e : \{ 0,1\} \hookrightarrow \Gamma \) a bit embedding, and suppose \(M\) computes the string function \(f : \{ 0,1\} ^* \to \{ 0,1\} ^*\) via \(e\) within time \(T\): for every binary string \(x\), the run of \(M\) on the letterwise \(e\)-image of \(x\) halts within \(T(\left\lvert x\right\rvert )\) steps with output the letterwise \(e\)-image of \(f(x)\). If, in the run of \(M\) on the \(e\)-image of some binary input \(x\), the transition taken from the configuration reached after \(t\) steps emits a symbol \(a \in \Gamma \), then \(a = e(b)\) for some bit \(b\).
Let \(\Gamma \) be a finite alphabet, \(E\) an injective block code of \(\Gamma \cup \{ \text{blank}\} \) into blocks of \(N+1\) optional bits that sends the blank to the all-blank block, \(e : \{ 0,1\} \hookrightarrow \Gamma \) a bit embedding, and \(M\) a Turing machine over \(\Gamma \). If, started on the letterwise \(e\)-image of a binary string \(x\), \(M\) halts within \(t\) steps with output the letterwise \(e\)-image of a binary string \(w\), then the binary block-code simulator, started on the input \(x\) itself, halts within \((3(N+1)+2)\cdot t\) steps with output \(w\).
[AB09, Claim 1.5]. Let \(\Gamma \) be a finite alphabet, \(e : \{ 0,1\} \hookrightarrow \Gamma \) an embedding of the two bits, \(M\) a Turing machine over \(\Gamma \) (with a read-only input tape, a write-only output tape, and \(k\) work tapes), \(f\) a function on binary strings, and \(T : \mathbb {N} \to \mathbb {N}\). Suppose \(M\) computes \(f\) via \(e\) within time \(T\): for every binary string \(x\), the run of \(M\) on the letterwise \(e\)-image of \(x\) halts within \(T(\left\lvert x\right\rvert )\) steps with output the letterwise \(e\)-image of \(f(x)\). Then there exist a constant \(c \in \mathbb {N}\) and a Turing machine \(M'\) over the binary alphabet with the same number \(k\) of work tapes such that \(M'\) computes \(f\) within time \(n \mapsto c\, (T(n)+1)\).