213 Complexity — Primitives
213.1 Overview
This module builds the primitive catalog of the machine-construction library: small multi-tape Turing machines over the binary alphabet — fixed-prefix emission, duplication into the self-delimiting pair code, fixed-width increment, pair-code validity testing and component extraction, unary polynomial generation, and length comparison against a captured result — each verified by exact run invariants and packaged as an existential machine contract with an explicit linear or polynomial time bound. Throughout, bits are written \(0\) and \(1\), words are elements of \(\{ 0,1\} ^*\), and the self-delimiting pair code of \((a,b)\) doubles each bit of \(a\), then appends the separator bits \(0,1\), then \(b\).
213.2 Declarations
For a fixed word \(w \in \{ 0,1\} ^*\), a finite Turing machine with no work tapes and \(\left\lvert w\right\rvert +1\) control states that first writes the bits of \(w\) to its output tape, one per step, and then copies its input to the output verbatim.
A configuration of the fixed-prefix emitter on input \(x\), specified by an optional control state, an input-head position, and the output written so far; the machine has no work tapes, so the work-tape fields are trivial.
For every \(i \le \left\lvert w\right\rvert \), after \(i\) steps from its initial configuration on input \(x\) the fixed-prefix emitter for \(w\) is in control state \(i\), the input head has not moved, and the output is the first \(i\) bits of \(w\).
For every \(i \le \left\lvert x\right\rvert \), after \(i\) steps from the configuration in which the whole fixed word \(w\) has been emitted and the input head sits at the start of \(x\), the prefix emitter has advanced the input head by \(i\) cells and its output is \(w\) followed by the first \(i\) bits of \(x\).
For every fixed word \(w\) and every input \(x\), the prefix emitter for \(w\) halts on \(x\) within \(\left\lvert w\right\rvert + \left\lvert x\right\rvert + 1\) steps, and its output is the concatenation \(w x\); the final step is the halting transition on the right blank.
A configuration of a machine with no work tapes on input \(x\), given by an optional control state, the number \(i \le \left\lvert x\right\rvert \) of input cells already passed, and the output written so far.
In a scan configuration indexed by \(i \le \left\lvert x\right\rvert \), the symbol under the input head is the \(i\)-th bit of \(x\) when \(i \lt \left\lvert x\right\rvert \), and the blank when \(i = \left\lvert x\right\rvert \).
Suppose a control state \(q\) of a machine without work tapes emits each scanned bit and moves right, and halts silently on the blank. Then for every \(j \le \left\lvert x\right\rvert \), \(j\) steps from the scan configuration at position \(0\) with prior output \(o\) lead to the scan configuration at position \(j\) in state \(q\) with output \(o\) followed by the first \(j\) bits of \(x\).
Suppose a control state \(q\) of a machine without work tapes emits each scanned bit and moves right, and halts silently on the blank. Then \(\left\lvert x\right\rvert +1\) steps from the scan configuration at position \(0\) with prior output \(o\) reach a halted configuration with output \(o\) followed by all of \(x\).
A five-state machine without work tapes that transforms its input \(x\) into the self-delimiting pair code of \((x,x)\): on a first pass it emits every input bit twice, then it emits the separator bit \(0\), rewinds to the start, emits the separator bit \(1\), and copies \(x\) once more.
For every \(j \le \left\lvert x\right\rvert \), after \(2j\) steps from its initial configuration on input \(x\) the duplicator is in its scanning state at input position \(j\) and has emitted each of the first \(j\) bits of \(x\) twice.
On every input \(x\) the duplicator halts within \(4(\left\lvert x\right\rvert +1)\) steps with output the self-delimiting pair code of \((x,x)\): each bit of \(x\) doubled, then the separator bits \(0,1\), then \(x\).
Suppose a control state \(q\) of a machine without work tapes emits each scanned bit and moves right, and halts silently on the blank. If \(x = p s\) is a split of the input into a prefix \(p\) and suffix \(s\), then \(\left\lvert s\right\rvert +1\) steps from the scan configuration at position \(\left\lvert p\right\rvert \) in state \(q\) with prior output \(o\) reach a halted configuration with output \(o\) followed by \(s\).
Suppose a control state \(q\) of a machine without work tapes moves right on reading a \(1\), emitting a \(0\) when an emission flag is set and nothing otherwise. If the first \(j \le \left\lvert x\right\rvert \) bits of \(x\) are all \(1\), then \(j\) steps from the scan configuration at position \(0\) in state \(q\) with empty output lead to position \(j\) in state \(q\), with output \(j\) zeros when the flag is set and empty output otherwise.
Every word \(x \in \{ 0,1\} ^*\), read least-significant bit first, satisfies exactly one of the following: \(x\) consists entirely of ones and its fixed-width increment overflows (is undefined); or \(x = 1^j 0 r\) for some \(j \ge 0\) and tail \(r\), and the fixed-width increment of \(x\) is \(0^j 1 r\).
The fixed-width increment machine is a four-state machine without work tapes computing the fixed-width binary increment of its input, read least-significant bit first: it scans the leading ones silently, and on reaching a \(0\) it rewinds and re-scans, emitting a \(0\) for each carried \(1\), a \(1\) in place of the first \(0\), and the remaining bits unchanged; an all-ones input halts with empty output.
On every input \(x\), including the empty word, the increment machine halts within \(3(\left\lvert x\right\rvert +1)\) steps; its output is the fixed-width binary increment of \(x\) (least-significant bit first) when no overflow occurs, and is empty when \(x\) consists entirely of ones.
If at control state \(q\) and input position \(i \lt \left\lvert x\right\rvert \) the transition of a machine without work tapes moves right, optionally emits a bit \(e\), and passes to state \(q'\), then one step from the scan configuration at \(i\) with output \(o\) yields the scan configuration at \(i+1\) in state \(q'\) with output \(o\) extended by \(e\) when present.
A machine without work tapes that checks membership in the self-delimiting pair code: it scans its input in aligned two-bit blocks, remembering the first bit of the current block in its finite control, continues silently while the two bits of a block agree, and halts with a one-bit verdict at the first disagreement or boundary blank; the verdict is \(1\) exactly when the disagreeing block is \(01\).
If the input splits as \(x = p\, b\, c\, r\) with bits \(b, c\), then two steps of the validity tester from its block state at position \(\left\lvert p\right\rvert \) continue silently to the block state at position \(\left\lvert p\right\rvert +2\) when \(b = c\), and otherwise halt at position \(\left\lvert p\right\rvert +2\) with single-bit output that is \(1\) exactly when \((b,c) = (0,1)\).
For any split \(x = p s\) of the input, there is a time \(t \le \left\lvert s\right\rvert +1\) such that after \(t\) steps from the block state at position \(\left\lvert p\right\rvert \) with empty output, the validity tester has halted and its output is the single bit recording whether \(s\) is a valid self-delimiting pair code.
For every input \(x\), the pair-validity tester halts on \(x\) within \(\left\lvert x\right\rvert +1\) steps, and its output is the single bit recording whether \(x\) decodes under the self-delimiting pair code.
A one-work-tape machine, parameterized by two Boolean flags, that parses an input in the self-delimiting pair code of \((a,b)\): it buffers the decoded first component \(a\) on its work tape while validating the doubled prefix, and after the separator it rewinds and replays the buffer, emitting \(a\) when the first flag is set, then scans the suffix, emitting \(b\) when the second flag is set; invalid inputs make it halt silently.
Given an input \(x\), an optional control state, an input position \(i \le \left\lvert x\right\rvert \), a buffered word \(a\), a work-head displacement \(z\), and an output word, the extractor configuration is the configuration of the pair extractor with that control state, with its input head past the first \(i\) cells, with \(a\) stored on its single work tape and the work head at \(z\), and with the given output.
In an extractor configuration at input position \(i \le \left\lvert x\right\rvert \), the symbol under the input head is the \(i\)-th bit of \(x\) when \(i \lt \left\lvert x\right\rvert \) and the blank otherwise, regardless of the buffer contents.
If the input splits as \(x = p\, b\, r\) with bit \(b\), one step of the pair extractor from its block-start state at position \(\left\lvert p\right\rvert \) records \(b\) in the finite control and advances the input head, leaving the buffer and the output unchanged.
If the input splits as \(x = p\, b\, c\, r\) with bits \(b, c\), then two extractor steps from the block-start state at position \(\left\lvert p\right\rvert \) with buffer \(a\) append \(b\) to the buffer and continue when \(b = c\); halt silently when \((b,c) = (1,0)\); and enter the rewind phase with the work head one cell before the end of the buffer when \((b,c) = (0,1)\). In all three cases nothing is emitted.
From the extractor’s rewind state with buffer \(a\) and work head at displacement \(j-1\), for any \(j \le \left\lvert a\right\rvert \), exactly \(j+1\) steps return the work head to displacement \(0\) and enter the replay state, with the input position, the buffer, and the (empty) output unchanged.
From the extractor’s replay state with buffer \(a\) and work head at displacement \(0\), for any \(j \le \left\lvert a\right\rvert \), exactly \(j\) steps move the work head to displacement \(j\) and emit the first \(j\) bits of \(a\) when the first-component flag is set, and nothing otherwise.
From the extractor’s replay state with buffer \(a\) and work head at displacement \(0\), exactly \(\left\lvert a\right\rvert +1\) steps reach the suffix state with the work head at displacement \(\left\lvert a\right\rvert \), and the output is \(a\) when the first-component flag is set and empty otherwise.
With the second-component flag set and a split \(x = p s\) of the input, from the extractor’s suffix state at position \(\left\lvert p\right\rvert \) with buffer \(a\) and prior output \(o\), exactly \(\left\lvert s\right\rvert +1\) steps reach a halted configuration with output \(o\) followed by \(s\); the buffer and its head are untouched.
For a split \(x = p s\) of the input and a validated buffer \(a\), there is a time \(t \le 2\left\lvert a\right\rvert + \left\lvert s\right\rvert + 3\) such that after \(t\) steps from the start of the rewind phase at position \(\left\lvert p\right\rvert \) the extractor has halted, and its output is \(a\) (when the first flag is set) followed by \(s\) (when the second flag is set).
For any split \(x = p s\) of the input and any buffered prefix \(a\), there is a time \(t \le 3\left\lvert s\right\rvert + 2\left\lvert a\right\rvert + 5\) such that after \(t\) steps from the block-start state at position \(\left\lvert p\right\rvert \) the extractor has halted; if \(s\) decodes under the self-delimiting pair code as \((b,c)\), the output is \(a b\) (when the first flag is set) followed by \(c\) (when the second flag is set), and if \(s\) is not a valid pair code the output is empty.
On every input \(x\) the pair extractor halts within \(5(\left\lvert x\right\rvert +1)\) steps; if \(x\) decodes under the self-delimiting pair code as \((a,b)\), the output is \(a\) (when the first flag is set) followed by \(b\) (when the second flag is set), and if \(x\) is not a valid pair code the output is empty.
For parameters \(c\) and \(C\), the control-state type of the unary polynomial generator has a copy state, a setup state, a loop state and a rewind state for each of the \(c+1\) loop levels, an advance state for each of \(c+2\) indices (one per level and one past the last), and an emission state for each remaining count from \(0\) to \(C\).
The tape content holding the unary word of length \(q\): cell \(z\) contains a \(1\) for \(0 \le z \lt q\) and is blank otherwise.
Given a work-tape index \(i\), a direction \(d\), and a control state \(s\), the head-only move action is the action that moves work head \(i\) one cell in direction \(d\), keeps the input head and all other work heads in place, writes no tape cell, emits no output, and enters \(s\).
A machine with \(c+1\) work tapes that writes a run of \(C\, (n+1)^{c+1}\) ones on its output tape, where \(n\) is the input length: in one input scan it copies \(n+1\) in unary onto every work tape in parallel, and then runs \(c+1\) nested loops, each of side \(n+1\), emitting \(C\) ones at each visit of the innermost body; a completed inner loop is rewound at a cost charged to the iterations that just completed.
A configuration of the unary polynomial generator in which every work tape holds the unary word of length \(q\), with a given control state, arbitrary work-head positions, and accumulated output.
For every work-tape index \(i\) and direction \(d\), applying the head-only move action for \(i\), \(d\), and a target state to a generator loop configuration yields the loop configuration in that target state whose \(i\)-th work-head position is increased by \(d\); all tapes, the input position, the other heads, and the output are unchanged.
From the generator’s emission state with counter \(j \le C\), exactly \(j+1\) steps append \(j\) ones to the output and enter the innermost advance state, leaving every head position unchanged.
From the rewind state of loop level \(i\) with head \(i\) at displacement \(j-1\), for any \(j \le q\), exactly \(j+1\) steps reset head \(i\) to displacement \(0\) and enter the advance state of level \(i+1\); the other loop heads and the accumulated output are unchanged.
For every loop level \(i\), one step of the generator from the advance state of level \(i\) yields the loop state of level \(i\) with head \(i\) moved one cell to the right, everything else being unchanged.
For a side length \(q\), an emission count \(C\), and a number \(r\) of loop levels, the exact running time \(T_r\) of a full nest of unary loops is defined by \(T_0 = C + 1\) and \(T_{r+1} = q\, (T_r + 2) + q + 2\).
Let \(q \gt 0\) be the unary side length, let \(i \le c\) be a loop level, and suppose every head at a level \(\le i\) is at displacement \(0\) except that head \(i\) sits at \(j\), where \(j + r = q\). Then exactly \(r\, (T_i + 2) + q + 2\) steps (with \(T_i\) the exact level-\(i\) nest cost) execute the remaining \(r\) iterations of loop \(i\), append \(r \cdot C q^i\) ones to the output, reset head \(i\) to \(0\), and enter the advance state of level \(i+1\); heads above level \(i\) are arbitrary and remain unchanged.
For every \(q\), writing a \(1\) at cell \(q\) of the unary tape of length \(q\) yields the unary tape of length \(q+1\).
For every side length \(q \gt 0\), emission count \(C\), and number of levels \(r\), the exact nest cost satisfies \(T_r \le (C + 1 + 5r)\, q^r\).
The generator’s configuration after scanning \(i \le \left\lvert x\right\rvert \) input cells in its copy phase: every work tape holds the unary word of length \(i\) and the input head has passed \(i\) cells.
For every \(i \le \left\lvert x\right\rvert \), after \(i\) steps from the generator’s initial configuration on input \(x\) the machine is in the copy-phase configuration with \(i\) unary marks on every work tape.
From the generator’s setup state with all work heads at displacement \(j-1\), for any \(j \le q\), exactly \(j+1\) steps move all heads to displacement \(0\) in lockstep and enter the outermost loop state, with empty output throughout.
For every input \(x\), running the generator for exactly \(2(\left\lvert x\right\rvert +1)\) steps from its initial configuration yields the configuration in which every work tape holds the unary word of length \(\left\lvert x\right\rvert +1\), the control is in the outermost loop state, all heads are at displacement \(0\), and the output is empty; the extra unary cell makes empty input need no special case.
For all parameters \(c\) and \(C\), the unary polynomial generator computes the function sending a word of length \(n\) to the run of \(C\, (n+1)^{c+1}\) ones, within \((C + 5(c+1) + 4)\, (n+1)^{c+1}\) steps; this covers coefficient \(C = 0\) and empty input.
For a machine \(M\), the administrative action of the length checker built over \(M\), given an input direction, a countdown direction, an optional bit, and a target state, is the action that moves the input head and the final (countdown) work head by those directions, emits the optional bit, passes to the target state, and writes no tape cell.
Given a machine \(M\), the captured-length checker over \(M\) is a machine with one additional work tape that first simulates \(M\) on the input while capturing the output of \(M\) on the extra tape, rewinds the input head to the start, parses the input’s doubled prefix under the self-delimiting pair grammar, and after the separator compares the length of the remaining suffix against the length of the captured word, emitting a single Boolean verdict; only the final comparison or a rejection emits output.
Given a machine \(M\), an input \(x\), a configuration \(c\) of \(M\) on \(x\), a checker control state, an input position \(i \le \left\lvert x\right\rvert \), and a counter \(r\), the length-checker configuration retains the tape bank of \(c\) together with the output of \(c\) captured on the extra tape, has the given control state and its input head past the first \(i\) cells, and places the capture head at displacement \(r - 1\), so that \(r\) countdown cells remain available.
For every input \(x\) and every position \(i \le \left\lvert x\right\rvert \), in a length-checker configuration at input position \(i\) the input head reads the \(i\)-th bit of \(x\) (the blank when \(i = \left\lvert x\right\rvert \)), independently of the saved tape bank.
Applying an administrative action with compatible input-head and countdown-head moves to a length-checker configuration yields the checker configuration with the correspondingly updated input position and countdown counter, with output equal to the action’s optional emission and all work tapes unchanged.
For a split \(x = p s\) of the input and a counter \(r\) at most the captured word’s length, from the checker’s comparison state at position \(\left\lvert p\right\rvert \) there is a time \(t \le \left\lvert s\right\rvert + 1\) such that after \(t\) steps the checker has halted with output the single bit recording whether \(\left\lvert s\right\rvert \le r\); the empty suffix succeeds even with counter \(0\).
If the input splits as \(x = p\, b\, s\) with bit \(b\), one checker step from the block-start parse state at position \(\left\lvert p\right\rvert \) records \(b\) in the finite control and advances the input head; the countdown cells and the output are untouched.
If the input splits as \(x = p\, b\, d\, s\) with bits \(b, d\), two checker steps from the block-start parse state at position \(\left\lvert p\right\rvert \) continue silently at position \(\left\lvert p\right\rvert +2\) when \(b = d\); halt with verdict \(0\) when \((b,d) = (1,0)\); and enter the suffix length comparison when \((b,d) = (0,1)\). The countdown counter is unchanged in every case.
For a split \(x = p s\) of the input and a counter \(r\) at most the captured word’s length, from the checker’s block-start parse state at position \(\left\lvert p\right\rvert \) there is a time \(t \le \left\lvert s\right\rvert + 1\) after which the checker has halted with a one-bit output: if \(s\) decodes under the self-delimiting pair code as \((a,b)\), the bit records whether \(\left\lvert b\right\rvert \le r\), and if \(s\) is malformed the bit is \(0\).
Suppose a machine has a start state that unconditionally moves the input head left into a scanning state, and the scanning state keeps moving left on symbols and exits right into a destination state on the left blank. Then from any configuration \(c\) in the start state there is a time \(r \le i + 2\), where \(i\) is the current input position, after which the machine is in the destination state with the input head back at the first cell, all tapes and the output unchanged.
Let \(M\) be a machine that, on input \(x\), halts within \(T\) steps with output \(w\). Then within \(T + \left\lvert x\right\rvert + 4\) steps the length checker built over \(M\) reaches, without emitting any physical output, the checker configuration at input position \(0\) in its parse state, retaining a halted bank of \(M\) whose captured output is \(w\) and with all \(\left\lvert w\right\rvert \) countdown cells available.
Let \(M\) compute the total function \(g\) within time \(T\). Then the length checker built over \(M\) computes, within \(T(n) + 2n + 5\) steps on inputs of length \(n\), the one-bit function that on input \(x\) outputs whether \(\left\lvert b\right\rvert \le \left\lvert g(x)\right\rvert \) when \(x\) decodes under the self-delimiting pair code as \((a,b)\), and outputs \(0\) when \(x\) is malformed.
A four-state, one-work-tape machine that copies its input to the work tape, then erases the trailing run of zeros and the last \(1\) from the right, rewinds, and replays the retained prefix to the output; an input containing no \(1\) halts silently during the reverse scan.
Given an input \(x\), an optional control state, an input position \(i \le \left\lvert x\right\rvert \), a buffer word \(w\), a head displacement \(h\), and an output word, the stripping-machine configuration is the configuration of the marker-stripping machine with that control state, with its input head past the first \(i\) cells, with \(w\) stored contiguously on its work tape and the work head at \(h\), and with the given output.
Blanking the cell at position \(\left\lvert w\right\rvert \) of the tape holding the buffered word \(w b\) (for any final bit \(b\)) yields exactly the tape holding the buffered word \(w\).
For every \(j \le \left\lvert x\right\rvert \), after \(j\) steps from its initial configuration on input \(x\) the stripping machine holds the first \(j\) bits of \(x\) on its work tape with both heads advanced by \(j\), and has emitted nothing.
From the stripping machine’s rewind state with buffer \(a\) and work head at displacement \(j-1\), for any \(j \le \left\lvert a\right\rvert \), exactly \(j+1\) steps return the work head to displacement \(0\) and enter the replay state, emitting nothing.
From the stripping machine’s replay state with buffer \(a\) and work head at displacement \(0\), for any \(j \le \left\lvert a\right\rvert \), exactly \(j\) steps move the work head to displacement \(j\) and emit the first \(j\) bits of \(a\), preserving the buffer.
From the stripping machine’s rewind state with retained buffer \(a\) and work head at displacement \(\left\lvert a\right\rvert -1\), exactly \(2(\left\lvert a\right\rvert +1)\) steps reach a halted configuration whose output is exactly \(a\).
One step of the stripping machine in its reverse state with buffer \(w b\) and work head on the final cell erases that cell and moves left, entering the rewind state when the erased bit \(b\) is \(1\) and staying in the reverse state when \(b\) is \(0\).
From the stripping machine’s reverse state with buffer \(w\) and work head on the final cell, there is a time \(t \le 3(\left\lvert w\right\rvert +1)\) after which the machine has halted; its output is the prefix of \(w\) strictly before the last \(1\) bit of \(w\), and is empty when \(w\) contains no \(1\).
For every \(n\) and every input \(x\) of length \(n\), the marker-stripping machine halts within \(4(n+1)\) steps, and its output is the prefix of \(x\) strictly before its last \(1\) bit, or the empty word when \(x\) contains no \(1\).
A one-state machine without work tapes that scans its input left to right, advancing silently over zeros, and halts with the one-bit verdict recording whether the input contains a \(1\) bit.
For any split \(x = p s\) of the input, there is a time \(t \le \left\lvert s\right\rvert + 1\) such that after \(t\) steps from the scan configuration at position \(\left\lvert p\right\rvert \) with empty output, the marker-existence scanner has halted with output the single bit recording whether \(s\) contains a \(1\).
For every \(n\) and every input of length \(n\), the marker-existence scanner halts within \(n+1\) steps, and its output is the single bit recording whether the input contains a \(1\) bit.
If a word \(x\) decodes under the self-delimiting pair code as the pair \((a,v)\), then \(x\) is exactly the pair encoding of \((a,v)\): each bit of \(a\) doubled, then the separator bits \(0,1\), then \(v\).
Every word \(v\) satisfies exactly one of: \(v\) contains no \(1\) and the last-marker split of \(v\) is undefined; or \(v\) contains a \(1\) and the last-marker split of \(v\) is some word \(u\) (the prefix of \(v\) strictly before its last \(1\)) such that moreover, for every prefix \(p\), the last-marker split of \(p v\) is \(p u\).
For every word \(x\), the second component extracted from \(x\) under the self-delimiting pair code (taken empty when \(x\) is malformed) has length at most \(\left\lvert x\right\rvert \).
Let a machine compute the total function \(g\) within a monotone time bound \(T_g\). Then the buffered composition of the second-component pair extractor with that machine computes, within \(6(n+1) + T_g(n) + 1\) steps on inputs of length \(n\), the function sending \(x\) to \(g(b)\), where \(b\) is the second component of \(x\) under the self-delimiting pair code (the empty word when \(x\) is malformed).
For every fixed word \(w \in \{ 0,1\} ^*\) there exist a finite Turing machine \(M\) and a constant \(c\) (which may depend on \(w\)) such that \(M\) computes the function \(x \mapsto w x\) (prepend \(w\) to the input) within \(c\, (n+1)\) steps on inputs of length \(n\).
There exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes the function sending each input \(x\) to the little-endian binary representation of \(\left\lvert x\right\rvert \), within \(c\, (n+1)\) steps on inputs of length \(n\).
For all constants \(C\) and \(e\) there exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes the function sending each input of length \(n\) to the run of \(C\, (n+1)^{e}\) ones, within \(c\, (n+1)^{e+1}\) steps.
For all constants \(C\) and \(e\) there exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes the function sending each input of length \(n\) to the little-endian binary representation of \(C\, (n+1)^{e}\), within \(c\, (n+1)^{e+1}\) steps.
For every fixed word \(\alpha \) there exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes the function sending \(x\) to the self-delimiting pair encoding of \((\alpha , x)\) — each bit of \(\alpha \) doubled, the separator bits \(0,1\), then \(x\) — within \(c\, (n+1)\) steps on inputs of length \(n\).
There exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes, within \(c\, (n+1)\) steps on inputs of length \(n\), the function sending a word in the self-delimiting pair code to the first component of the encoded pair, and any malformed word to the empty word.
There exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes, within \(c\, (n+1)\) steps on inputs of length \(n\), the function sending a word in the self-delimiting pair code to the second component of the encoded pair, and any malformed word to the empty word.
There exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes, within \(c\, (n+1)\) steps on inputs of length \(n\), the one-bit function recording whether the input is a valid word of the self-delimiting pair code.
There exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes, within \(c\, (n+1)\) steps on inputs of length \(n\), the function sending a word that encodes the pair \((a,b)\) under the self-delimiting pair code to the concatenation \(a b\), and any malformed word to the empty word.
There exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes, within \(c\, (n+1)\) steps on inputs of length \(n\), the function sending \(x\) to the self-delimiting pair encoding of \((x,x)\): each bit of \(x\) doubled, the separator bits \(0,1\), then \(x\).
For a machine \(M\), an action of the threaded-map controller built over \(M\): it moves the input head and the final (capture) work head by the given directions, optionally emits one output bit, and passes to the given control state, writing no tape cell.
Given a machine \(M\), the threaded-map controller over \(M\) is a machine with one extra work tape that first simulates \(M\) on the input while capturing the output of \(M\) on the extra tape, rewinds the capture head and the input, silently validates the input’s membership in the self-delimiting pair code, and only on success rewinds the input once more and emits the input’s doubled prefix and separator followed by the captured word; malformed inputs halt without any emission.
A configuration of the threaded-map controller that preserves the completed tape bank of the simulated machine and its captured word, and records the controller’s state, the input position, the capture-head displacement, and the output written so far.
Applying an administrative action of the threaded-map controller moves the input position and the capture-head displacement by the specified directions, installs the designated control state, and appends the optional emission to the output; no work-tape cell changes.
From the controller’s capture-rewind state with the capture head at displacement \(j-1\), for any \(j\) at most the captured word’s length, exactly \(j+1\) silent steps return the capture head to displacement \(0\) and enter the input-rewind phase, with the input position unchanged.
Let \(M\) be a machine that, on input \(x\), halts within \(T\) steps with output \(w\). Then within \(T + \left\lvert w\right\rvert + \left\lvert x\right\rvert + 5\) steps the threaded-map controller built over \(M\) reaches, without emitting any physical output, its silent validation state at input position \(0\) with the capture head at \(0\), retaining a halted bank of \(M\) whose captured output is \(w\).
In a threaded-map configuration whose input head has passed \(i \le \left\lvert x\right\rvert \) cells, the symbol read is the \(i\)-th bit of \(x\) (the blank when \(i = \left\lvert x\right\rvert \)), independently of the preserved bank.
If the input splits as \(x = p\, b\, s\) with bit \(b\), one step of the threaded-map controller from its block-start parse state at position \(\left\lvert p\right\rvert \) records \(b\) in the finite control and advances the input head, emitting \(b\) exactly when the controller is in its emitting (replay) pass.
If the input splits as \(x = p\, b\, d\, s\) with bits \(b, d\), two steps of the threaded-map controller from its block-start parse state at position \(\left\lvert p\right\rvert \) continue parsing when \(b = d\), halt when \((b,d) = (1,0)\), and pass to the post-separator state when \((b,d) = (0,1)\); both bits are emitted exactly when the controller is in its emitting pass. The captured word and its head are preserved.
For a split \(x = p s\) of the input, there is a time \(t \le \left\lvert s\right\rvert + 1\) from the controller’s silent validation state at position \(\left\lvert p\right\rvert \) such that: if \(s\) is a valid word of the self-delimiting pair code, after \(t\) steps the controller is at its post-validation state with nothing emitted; and if \(s\) is malformed, after \(t\) steps the controller has halted with empty output.
If the input splits as \(x = p\) followed by the pair encoding of \((a,b)\), then from the controller’s emitting parse state at position \(\left\lvert p\right\rvert \) with prior output \(o\), exactly \(2\left\lvert a\right\rvert + 2\) steps emit the doubled word \(a\) and the separator bits \(0,1\), and enter the captured-payload replay state with the capture head still at displacement \(0\).
For every \(j\) at most the captured word’s length and every prior output \(o\), running the controller for exactly \(j\) steps from its payload-replay state with the capture head at displacement \(0\) yields the payload-replay configuration with the capture head at displacement \(j\) and output \(o\) followed by the first \(j\) captured bits; the bank is preserved.
From the controller’s payload-replay state with the capture head at displacement \(0\) and prior output \(o\), after one more step than the captured word’s length the controller has halted with output \(o\) followed by the entire captured word.
For all words \(a\) and \(b\), the self-delimiting pair encoding of \((a,b)\) has length exactly \(2\left\lvert a\right\rvert + 2 + \left\lvert b\right\rvert \).
Let \(M\) compute the total function \(f\) within time \(T\). Then the threaded-map controller built over \(M\) computes, within \(4(T(n) + n + 3)\) steps on inputs of length \(n\), the function sending a word \(x\) that decodes under the self-delimiting pair code with first component \(a\) to the pair encoding of \((a, f(x))\), and any malformed word to the empty word.
Let a machine compute the total function \(g\) within a monotone time bound \(T_g\). Then there exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes, within \(c\, (n + 1 + T_g(n))\) steps on inputs of length \(n\), the function sending a word that encodes the pair \((a,b)\) under the self-delimiting pair code to the pair encoding of \((a, g(b))\), and any malformed word to the empty word.
For all constants \(C\) and \(e\) there exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes, within \(c\, (n+1)^{e+1}\) steps on inputs of length \(n\), the one-bit function that on a word encoding the pair \((a,b)\) under the self-delimiting pair code outputs whether \(\left\lvert b\right\rvert \le C\, (\left\lvert a\right\rvert +1)^{e}\), and on any malformed word outputs \(0\).
There exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes, within \(c\, (n+1)^{2}\) steps on inputs of length \(n\), the following function: a word encoding the pair \((a,v)\) under the self-delimiting pair code, where \(v\) contains a \(1\) and \(u\) is the prefix of \(v\) strictly before its last \(1\), is sent to the pair encoding of \((a,u)\); a word whose second component contains no \(1\), or any malformed word, is sent to the empty word.
For a word \(w\), the split-search step sends a candidate word \(s\) with \(\left\lvert s\right\rvert \le \left\lvert w\right\rvert \) to \(s\) followed by one \(1\) bit, and sends any longer candidate to itself.
The acceptance test of the split search with parameters \(C\) and \(e\): a candidate \(s\) is accepted for the word \(w\) exactly when \(\left\lvert s\right\rvert + C\, (\left\lvert s\right\rvert +1)^{e} = \left\lvert w\right\rvert \).
If a candidate \(s\) has length at most \(\left\lvert w\right\rvert + 1\), then so does the result of one split-search step on \(s\).
For every \(i \le \left\lvert w\right\rvert + 1\), the \(i\)-th iterate of the split-search step on the empty candidate is the unary word \(1^i\).
If two Boolean predicates agree on every member of a list, then searching the list for the first element satisfying the one returns the same result as searching for the first element satisfying the other.
For all \(C\) and \(e\) and every word \(w\), searching the indices \(0, \dots , \left\lvert w\right\rvert \) for the first \(i\) at which the split-acceptance test succeeds on the \(i\)-th iterate of the split step returns exactly the arithmetic split search at parameters \(C\), \(e\), and \(\left\lvert w\right\rvert \), i.e. the least \(i\) with \(i + C\, (i+1)^{e} = \left\lvert w\right\rvert \) when one exists and nothing otherwise.
The arithmetic split search at parameters \(C\), \(e\), and \(\left\lvert w\right\rvert \) fails if and only if the split-acceptance test rejects the \(i\)-th iterate of the split step on the empty candidate for every \(i \le \left\lvert w\right\rvert \).
Splitting \(w\) at the length of the first accepted orbit candidate and pair encoding the two halves gives the same word as splitting \(w\) at the index returned by the arithmetic split search; when both searches fail, both sides are the empty word.
For all naturals \(c\), \(A\), \(e\), \(n\),
For an input \(w\) and a count \(j\), the saturated input position is \(\min (j, \left\lvert w\right\rvert ) + 1\): the physical input-head position after consuming \(j\) cells, saturated at the right boundary.
In any configuration whose input head is at the saturated position for \(j\) on input \(w\), the symbol read is the \(j\)-th bit of \(w\) when \(j \lt \left\lvert w\right\rvert \) and the blank otherwise.
For every input \(w\) and every count \(j\), moving the input head one cell to the right from the saturated position for \(j\) on \(w\) yields the saturated position for \(j+1\).
The tape content of a unary scratch word of length \(q\) whose first \(j\) cells have been cleared: cell \(z\) holds a \(1\) for \(j \le z \lt q\) and is blank otherwise.
For all \(q\) and \(j\), blanking cell \(j\) of the unary scratch tape of length \(q\) with \(j\) cells already cleared yields the scratch tape with \(j+1\) cells cleared.
For \(k\) scratch tapes, a machine with \(k+1\) work tapes implementing the rejection cleanup of the split search: it scans the candidate word on the first work tape while clearing every unary scratch tape, appends one \(1\) bit to the candidate exactly when the candidate’s length does not exceed the input length, rewinds all work heads along the candidate and then rewinds the input head, and finally stalls in an absorbing return state.
A configuration of the cleanup machine in which \(j\) candidate cells have been consumed, exactly that prefix has been erased on each scratch tape, and the physical input head tracks the same count at its saturated position.
For every \(j\) at most the candidate’s length, \(j\) steps of the cleanup machine from the start of its scan phase reach the cleanup scan configuration for \(j\), with nothing emitted; the overflow flag records exactly whether more candidate cells than input cells have been consumed.
A configuration of the cleanup machine in which only the candidate word remains, on the first work tape; all work heads sit at a common displacement and the physical output is empty.
One step of the cleanup machine from the end of its scan phase clears the final extra scratch cell and appends a \(1\) to the candidate exactly when the candidate’s length is at most the input length; the result is the cleaned configuration holding one split-search step applied to the candidate.
For every \(j\) at most the candidate’s length, exactly \(j+1\) steps of the cleanup machine from the cleaned configuration with all work heads at displacement \(j-1\) yield the cleaned configuration of the next phase with every work head at displacement \(0\); no candidate bit is altered.
For any input \(w\) and candidate \(s\), there is a time \(t \le 2\left\lvert s\right\rvert + \left\lvert w\right\rvert + 5\) after which the cleanup machine, started at the beginning of its scan phase, reaches the canonical anchored configuration, in its return state, whose stored words carry one split-search step applied to \(s\); every transition on the way is silent.
The transform that converts an action of a source machine into an action of the counting host: each output emission of the source becomes one rightward move of the native input head, the first work tape (holding the candidate) is untouched, the source’s tape writes and moves are reproduced on the successor-indexed tapes, nothing is emitted, and a finite flag records consumption past the native right boundary.
The configuration of the counting host that embeds a source configuration over the empty virtual input: the candidate \(s\) sits on the first work tape, the source’s work tapes occupy the remaining tapes, and the native input head is at the saturated position for \(\left\lvert s\right\rvert \) plus the length of the source’s output so far.
For a configuration whose input head is at the saturated position for \(j\) on input \(w\), the disjunction of the flag recording \(\left\lvert w\right\rvert \lt j\) with the test that the symbol read is blank equals the flag recording \(\left\lvert w\right\rvert \lt j + 1\).
Applying the transformed action to the counting-host embedding of a source configuration yields exactly the counting-host embedding of the source configuration after the original action: one native input cell is consumed per source emission, the candidate is preserved, and all source-bank writes and moves are reproduced.
Suppose the host machine’s transitions on embedded states agree with the emission-counting transform of the source machine’s transitions, and the source, started from a configuration \(c\) over the empty input, does not halt before time \(t\). Then \(t\) steps of the host from the embedding of \(c\) land exactly on the embedding of the source configuration after \(t\) steps; the host’s physical output stays empty throughout.
On the empty input, with every unary loop tape of side \(q \gt 0\) already installed and all heads at \(0\), the unary polynomial generator runs for exactly one more step than the exact nest cost at level \(c+1\) and halts, having emitted \(C\, q^{c+1}\) ones, with every loop head back at \(0\).
Let \(q\) be a control state on which the machine stalls (every configuration in state \(q\) is a fixed point of the step function), and suppose the run from \(c\) reaches a configuration \(d\) in state \(q\) after \(T\) steps. Then there is a time \(t \le T\) such that no configuration strictly before time \(t\) is in state \(q\) and the configuration at time \(t\) is already \(d\).
For any input \(w\) and candidate \(s\), there is a time \(t\) with \(0 \lt t \le 2\left\lvert s\right\rvert + \left\lvert w\right\rvert + 5\) such that the cleanup machine never visits its return state before time \(t\) and at time \(t\) sits in the canonical anchored return configuration carrying one split-search step applied to \(s\).
In the counting-host embedding of a source configuration, the conjunction of the negated overflow flag with the test that the native input read is blank holds exactly when the candidate’s length plus the source’s output length equals the input length.
Suppose the host’s transitions on embedded states agree with the emission-counting transform of the source’s transitions, and the source run from \(c\) reaches a halted configuration \(d\) after \(T\) steps. Then there is a time \(t \le T\) at which the host run from the embedding of \(c\) equals the embedding of \(d\).
For \(k\) scratch tapes, a machine with \(k+1\) work tapes that prepares the polynomial loop bank of the split search: it scans the candidate on the first work tape while writing its length in unary onto every scratch tape in parallel, adds one extra side-length cell, rewinds all work heads along the untouched candidate, and stalls in an absorbing return state.
A configuration of the preparation machine in which \(j\) candidate cells have been scanned and every scratch tape holds the unary word of length \(j\), with the input head at its saturated position for \(j\).
For every \(j\) at most the candidate’s length, \(j\) steps of the preparation machine from the start of its scan yield the preparation scan configuration for \(j\); the candidate is unchanged and nothing is emitted, and this holds also for candidates longer than the native input.
A configuration of the preparation machine in which every scratch tape holds the unary word of length one more than the candidate’s length, all work heads sit at a common displacement, and the finite flag records whether the candidate is longer than the input.
For every input \(w\) and candidate \(s\), one step of the preparation machine from the end of its scan yields the prepared configuration in its rewind phase, in which every scratch tape holds the unary word of length \(\left\lvert s\right\rvert +1\) and all work heads are at displacement \(\left\lvert s\right\rvert -1\); the uniform extra cell makes the empty candidate need no special case.
For every \(j\) at most the candidate’s length, exactly \(j+1\) steps of the preparation machine from the prepared configuration in its rewind phase with all work heads at displacement \(j-1\) yield the prepared configuration in its return phase with every head at displacement \(0\); each scratch tape keeps its extra unary cell.
For every input \(w\) and candidate \(s\), exactly \(2(\left\lvert s\right\rvert +1)\) silent steps of the preparation machine from the canonical anchored configuration whose stored words carry \(s\) yield the prepared configuration, in which every scratch tape holds the unary word of length \(\left\lvert s\right\rvert +1\) and every head is at displacement \(0\).
For any input \(w\) and candidate \(s\), there is a time \(t \le 2(\left\lvert s\right\rvert +1)\) such that the preparation machine, started from the canonical anchored configuration carrying \(s\), never visits its return state before time \(t\) and at time \(t\) sits in the prepared configuration with all heads at \(0\).
The property of a machine, an anchor control state, a start configuration \(c\), and a duration \(t\), that none of the configurations of the run from \(c\) at times \(0\) through \(t\) inclusive is in the anchor state.
If the run from \(c\) is anchor-free for \(u\) steps and the run continued from its configuration at time \(u\) is anchor-free for \(v\) further steps, then the run from \(c\) is anchor-free for \(u + v\) steps.
Let a source machine have a class of terminal control states on which it stalls, and let a host machine agree, on the images of non-terminal states under a state embedding, with the mapped source transitions, where no embedded state equals a distinguished host anchor. If the source run from \(c\) reaches a terminal configuration \(d\) within \(T\) steps, then there is a \(t \le T\) such that the host run from the embedded \(c\) reaches the embedded \(d\) at time \(t\) and the entire host trace up to time \(t\) avoids the anchor.
A three-state machine, with \(k+1\) work tapes it never writes, that moves its input head left to the left boundary and then one cell right, stalling in an absorbing return state.
A four-state machine with \(k+1\) work tapes that emits the self-delimiting pair encoding of a split of its native input: using the first work tape only as a length counter, it emits each native bit twice while the counter has cells left, then emits the separator bits \(0,1\), then copies the remaining native suffix verbatim; no counter bit is ever emitted.
The finite control of the combined split-search round body over a source state type: an anchor state, a preparation phase, a counting phase carrying a source state and an overflow flag, a check phase, an input-rewind phase carrying the acceptance bit, a restoration phase, and an emission phase; only restoration can return to the anchor.
Given a source machine \(M\) and a start state, the machine executing one round of the split search: from the anchor it dispatches to preparation, runs the embedded preparation machine, starts \(M\) on the prepared bank with its emissions counted against the native input, checks whether the consumed length matches the input length, rewinds the input carrying the verdict, and then either runs the split emitter (acceptance) or the rejection cleanup followed by an explicit return to the anchor.
A configuration of the source machine over the empty virtual input in which every work tape holds the unary word of length one more than the candidate’s length, all heads are at displacement \(0\), and the control state and output are given parameters.
On every input \(w\), the initial configuration of the round body equals the canonical anchored configuration whose stored words carry the empty candidate.
If a host machine’s transitions on all embedded states equal the mapped transitions of a source machine, then for every start configuration \(c\) and time \(t\), the host run from the embedded \(c\) equals the embedding of the source run from \(c\), including through halting.
For any input \(w\) and candidate \(s\), there is a time \(t \le 2(\left\lvert s\right\rvert +1)\) such that \(t+1\) steps of the round body from its preparation seam reach the counting-host embedding of the prepared source bank at the source’s start state, and the whole trace avoids the anchor.
If the source machine, started on the prepared bank, reaches the halted bank with output \(o\) after \(T\) steps, then there is a time \(t \le T\) at which the round body, started from the counting-host embedding of the start bank, reaches the embedding of the halted bank with output \(o\); the whole trace avoids the anchor.
For a configuration \(c\) of the rewind machine in its start state, there is a time \(t \le i + 2\), with \(i\) the current input position, such that the round body run from the rewind-phase embedding of \(c\) (carrying the acceptance bit) reaches the embedding of \(c\) with its input head back at the first cell and in the rewind machine’s return state; the whole trace avoids the anchor and preserves the source bank and output.
For any input \(w\) and candidate \(s\), there is a time \(t \le 2\left\lvert s\right\rvert + \left\lvert w\right\rvert + 5\) such that the round body, started from the restoration-phase embedding of the cleanup scan, reaches the canonical anchored-word configuration in the restoration phase’s return state carrying one split-search step applied to \(s\); the whole trace avoids the anchor.
Given an input \(w\), a candidate \(s\), an optional control state, a count \(j\), a counter-head position \(h\), and an output word, the emitter configuration is the configuration of the split emitter with that control state, with its input head at the saturated position for \(j\), with \(s\) on its first work tape and the head there at \(h\), with every scratch tape holding the unary word of length \(\left\lvert s\right\rvert +1\) and its head at \(0\), and with the given output.
Let the candidate’s length be at most \(\left\lvert w\right\rvert \). For every \(j\) at most the candidate’s length, \(2j\) steps of the split emitter from its start emit each of the first \(j\) bits of \(w\) twice and advance both the native head and the candidate counter to \(j\); candidate bits are read only for their presence.
Once the candidate counter is exhausted, two steps of the split emitter append the separator bits \(0,1\) to the output without moving the native head from the start of the suffix.
If the native input splits as \(w = p r\), then from the split emitter’s copy state at position \(\left\lvert p\right\rvert \) with prior output \(o\), exactly \(\left\lvert r\right\rvert +1\) steps copy \(r\) to the output and halt, preserving all work tapes; this includes the empty suffix with its final blank-reading halt.
If the candidate’s length \(\ell \) is at most \(\left\lvert w\right\rvert \), then exactly \(\ell + \left\lvert w\right\rvert + 3\) steps of the split emitter from its start produce the self-delimiting pair encoding of the split of \(w\) at position \(\ell \) (the first \(\ell \) bits paired with the rest) and halt; the candidate may contain any bit pattern.
If one machine step carries \(c\) to \(d\) and neither \(c\) nor \(d\) is in the anchor state, then the one-step run from \(c\) ends at \(d\) and is anchor-free.
If the run from \(c\) reaches \(d\) in exactly \(u\) anchor-free steps and the run from \(d\) reaches \(f\) in exactly \(v\) anchor-free steps, then the run from \(c\) reaches \(f\) in exactly \(u+v\) anchor-free steps.
Suppose the source machine, started on the prepared bank for candidate \(s\), reaches the halted bank with output \(o\) after \(T\) steps. Then there is a time \(t\) with \(0 \lt t \le T + 5\left\lvert s\right\rvert + 3\left\lvert w\right\rvert + 20\) such that the round body, started from the canonical anchored configuration carrying \(s\) on input \(w\), never revisits the anchor strictly between times \(0\) and \(t\), and at time \(t\): if \(\left\lvert s\right\rvert + \left\lvert o\right\rvert = \left\lvert w\right\rvert \) the body has halted with output the pair encoding of the split of \(w\) at position \(\left\lvert s\right\rvert \); otherwise the body is back at the canonical anchored configuration carrying one split-search step applied to \(s\).
Let a body machine with a distinguished anchor state satisfy a startup contract (within \(A(n+1)^{e+1}\) steps it reaches the anchored empty-candidate configuration without an earlier anchor visit) and a round contract (from the anchored configuration carrying any candidate of length at most \(n+1\), within \(A(n+1)^{e+1}\) steps and with no interior anchor visit, it either halts with the encoded split when the candidate satisfies the length equation, or returns to the anchor with the stepped candidate). Then there exist a machine \(M\) and a constant \(c\) computing, within \(c\, (n+1)^{e+2}\) steps, the function that sends \(w\) to the pair encoding of the split of \(w\) at the least \(i\) with \(i + C\, (i+1)^{e} = \left\lvert w\right\rvert \), and to the empty word when no such \(i\) exists.
For all \(c\) and \(C\) and every candidate \(s\), the unary polynomial generator with \(c+1\) loop levels and \(C\) emissions per innermost visit, started in its outermost loop state on the prepared bank for \(s\), halts after exactly one more step than the exact nest cost at side length \(\left\lvert s\right\rvert +1\), and its captured output is a run of \(C\, (\left\lvert s\right\rvert +1)^{c+1}\) ones.
The fixed-prefix emitter for the word \(1^C\), started on the empty virtual input in the bank for candidate \(s\) (it has no scratch tapes), halts after exactly \(C+1\) steps with captured output \(1^C\), the final step being the blank-reading halt.
For all naturals \(C\), \(e\), \(l\), \(n\), \(T\) with \(l \le n + 1\) and \(T \le (C + 1 + 5e)(l+1)^{e} + 1\),
Let a source machine, started on the prepared bank for any candidate \(s\), halt within \(B(\left\lvert s\right\rvert )\) steps with captured output a run of \(C\, (\left\lvert s\right\rvert +1)^{e}\) ones, where \(B(l) \le (C+1+5e)(l+1)^{e} + 1\). Then there exist a machine \(N\) and a constant \(c\) computing, within \(c\, (n+1)^{e+2}\) steps, the function sending \(w\) to the pair encoding of the split of \(w\) at the least \(i\) with \(i + C\, (i+1)^{e} = \left\lvert w\right\rvert \), and to the empty word when no such \(i\) exists.
For all constants \(C\) and \(e\) there exist a machine \(M\) and a constant \(c\) computing, within \(c\, (n+1)^{e+2}\) steps on inputs of length \(n\), the function sending \(w\) to the pair encoding of the split of \(w\) at the least \(i\) with \(i + C\, (i+1)^{e} = \left\lvert w\right\rvert \), and to the empty word when no such \(i\) exists.
For all constants \(C\) and \(e\) there exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes, within \(c\, (n+1)^{e+2}\) steps on inputs of length \(n\), the function that on input \(w\) searches for the least \(i \le \left\lvert w\right\rvert \) with \(i + C\, (i+1)^{e} = \left\lvert w\right\rvert \) and, on success, outputs the self-delimiting pair encoding of the first \(i\) bits of \(w\) paired with the rest of \(w\), and on failure outputs the empty word.
There exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes, within \(c\, (n+1)\) steps on inputs of length \(n\), the fixed-width binary successor of its input read least-significant bit first, with empty output on overflow (an all-ones input).
The acceptance test of the width-parametric split search: for a width function \(f\), a candidate \(s\) is accepted for the word \(w\) exactly when \(\left\lvert s\right\rvert + f(\left\lvert s\right\rvert ) = \left\lvert w\right\rvert \); no monotonicity of \(f\) is assumed.
For every function \(f\) and every word \(w\), searching the indices \(0, \dots , \left\lvert w\right\rvert \) for the first \(i\) at which the width-parametric acceptance test succeeds on the \(i\)-th iterate of the split step (the unary candidate \(1^i\)) returns exactly the width-parametric split search for \(f\) at length \(\left\lvert w\right\rvert \).
Splitting \(w\) at the length of the first orbit candidate accepted by the width-parametric test and pair encoding the two halves gives the same word as splitting \(w\) at the index returned by the width-parametric split search for \(f\); when both searches fail, both sides are the empty word.
For all naturals \(c\), \(A\), \(n\), \(t\),
Let a body machine with an anchor state satisfy a startup contract and a round contract with common envelope \(A\, (T_E(n+1) + n + 2)\), where the round from a candidate \(s\) of length at most \(n+1\) either halts with the encoded split of the input at \(\left\lvert s\right\rvert \) when \(\left\lvert s\right\rvert + f(\left\lvert s\right\rvert )\) equals the input length, or returns to the anchor with the stepped candidate, never visiting the anchor strictly inside. Then there exist a machine \(M\) and a constant \(c\) computing, within \(c\, (n+1)(T_E(n+1) + n + 2)\) steps, the function sending \(w\) to the pair encoding of the split of \(w\) at the least \(i\) with \(i + f(i) = \left\lvert w\right\rvert \), and to the empty word when no such \(i\) exists.
A single-state machine with no work tapes, used only to supply the empty inactive bank of the virtual-input wrapper; its own transition is never entered by the phase that uses it.
Given a machine \(M\), the candidate evaluator obtained by wrapping the virtual-input phase of the buffered composition over \(M\) with the capture transformer: \(M\) runs on a buffered candidate as virtual input, every emission lands on a final capture tape rather than the physical output, and completion passes to a live return state.
A configuration of the candidate evaluator in which the preserved candidate occupies the first work tape, the simulated machine’s work bank follows it, and the final tape captures every emission of the simulated machine; the physical input head stays at a fixed position and the physical output is empty.
Let the simulated machine, started from a configuration \(c\) over the candidate with a valid virtual-input tag, stay live for all times before \(t\). Then \(t\) steps of the candidate evaluator from the evaluator configuration of \(c\) land exactly on the evaluator configuration of the simulated machine’s configuration at time \(t\), with a valid tag.
The evaluator configuration of the simulated machine’s initial configuration on a candidate \(s\) — candidate buffered, source work bank blank, capture tape empty, all heads at zero — equals the canonical anchored configuration whose stored words carry \(s\), at the evaluator’s initial virtual state.
Let \(M\), on the candidate \(s\), halt within \(T\) steps with output \(o\). Then there is a time \(t \le T\) at which \(M\)’s run on \(s\) has first halted, with output \(o\) and a valid virtual tag, such that the candidate evaluator never visits its return state before time \(t\) and at time \(t\) sits in the evaluator configuration of \(M\)’s halted configuration, its capture tape holding exactly \(o\).
For words \(u, v\) and an index \(j\), the length-\((j+1)\) prefixes of \(u\) and \(v\) agree if and only if their length-\(j\) prefixes agree and their optional \(j\)-th entries agree; in particular a missing bit differs from a present bit.
A machine with two read-only word tapes that scans both in lockstep through their common right blank, accumulating in its finite control the Boolean record of whether all cells so far agree, then rewinds both heads to zero; the phase never emits, and empty words follow the same positive-time path.
Given a physical input \(w\), words \(u\) and \(v\), an input position \(p\), a control phase \(q\), a register bit \(b\), and a displacement \(h\), the comparator configuration is the configuration of the two-word comparator in state \((q, b)\) with input head at \(p\), with \(u\) on its first tape and \(v\) on its second, both heads at displacement \(h\), and empty physical output.
For words \(u, v\) and an index \(j \lt \max (\left\lvert u\right\rvert , \left\lvert v\right\rvert )\), it is not the case that both the \(j\)-th entry of \(u\) and the \(j\)-th entry of \(v\) are missing.
For every \(j \le \max (\left\lvert u\right\rvert , \left\lvert v\right\rvert )\), after \(j\) forward steps of the comparator the equality register records exactly whether the length-\(j\) prefixes of \(u\) and \(v\) agree, with both heads at \(j\); this includes mismatches caused by unequal lengths.
From the comparator’s rewind state with both heads at displacement \(j-1\), for any \(j \le \max (\left\lvert u\right\rvert , \left\lvert v\right\rvert )\), exactly \(j+1\) steps restore both heads to displacement \(0\) and enter the return state, preserving the comparison register.
For all words \(u\) and \(v\), whole-word comparison of \(u\) and \(v\) completes silently in exactly \(2(\max (\left\lvert u\right\rvert , \left\lvert v\right\rvert ) + 1)\) steps, ending in the return state with the register recording whether \(u = v\), both word tapes unchanged, and both heads back at zero.
The marker tape of a contiguous visited interval of a given left endpoint and width: exactly the cells of the interval are marked, independently of the simulated data.
For a data tape, a left endpoint \(m\), and a count \(j\), the partially cleared tape is blank at every cell \(z\) with \(m \le z \lt m + j\) and agrees with the data tape at every other cell.
Blanking the cell at offset \(j\) from the left endpoint of a tape whose first \(j\) interval cells are already cleared yields the tape with \(j+1\) interval cells cleared.
A four-state machine with three work tapes — data, interval marker, and origin marker — that clears a finite marked work interval natively: it scans left to the marked interval’s left end, clears data and marker in lockstep moving right, rewinds using the origin marker, and erases that marker at the origin, stalling silently in its return state. Blank holes in the data are permitted; all heads stay aligned.
A configuration of the interval cleaner on physical input \(w\): the three tapes hold the data, the interval marker, and the origin marker, with all three heads at a common displacement; the physical input head and output are untouched.
Let a marked interval have left endpoint \(m\) and width \(W\), and let \(j \lt W\). Then \(j+2\) steps of the cleaner, started in its initial scan state at offset \(j\) from the left end, yield its clearing state at the left end \(m\), regardless of blank holes in the data; the data, interval marker, and origin marker are unchanged.
For every data tape and every left endpoint, the tape obtained by clearing zero cells of the visited interval is the original data tape.
If the data tape is blank outside the visited interval, then clearing the entire interval produces the all-blank tape; no assumption is made about holes or values inside the interval.
Let a marked interval have left endpoint \(m\) and width \(W\), and let \(j \le W\). Then \(j\) steps of the cleaner from its clearing state at \(m\) yield the configuration in which the first \(j\) cells of both the data and the interval marker are cleared and all heads are at offset \(j\), while the origin marker is intact.
The tape obtained by blanking cell \(0\) of the tape holding the single-cell marker word is the all-blank tape.
For every \(n\), if the data and interval-marker tapes are already blank and the cleaner is in its rewind state at displacement \(n\), then exactly \(n+1\) steps return all heads to the origin and erase the origin marker, reaching the return state with all three tapes blank.
Let a marked interval of width \(W\) contain the origin (\(\mathrm{left} \le 0 \lt \mathrm{left} + W\)), let the data vanish outside it, and start the cleaner anywhere inside it. Then there is a time \(t\) with \(0 \lt t \le 3W + 4\) after which the cleaner is in its return state with all three tapes blank and all heads at the origin.
The marker tape of a closed interval of visited cells from a lower to an upper endpoint; the data it tracks may have arbitrary blank holes inside the span.
If \(\mathrm{lo} \le \mathrm{hi}\) and a head position \(h\) lies within one cell of the closed span \([\mathrm{lo}, \mathrm{hi}]\), then marking cell \(h\) turns the span marker into the marker of \([\min (\mathrm{lo}, h), \max (\mathrm{hi}, h)]\).
Given three families \(D\), \(V\), \(O\), each indexed by \(k\) positions, the three-bank layout is the family indexed by \(k + (k + k)\) positions that lists \(D\) first, then \(V\), then \(O\); it is used to place simulated data, visited-cell markers, and origin markers in corresponding slots.
Given a machine \(M\), the tracked evaluator that simulates \(M\) using two native steps per source step: an initialization step marks each origin in both marker banks, the first microstep of each round performs \(M\)’s action (moving the corresponding marker heads along), and the second stamps the newly reached head cells in the visited bank before possibly halting; the physical output is exactly \(M\)’s output.
The configuration of the tracked evaluator after a completed source step: the data bank holds the source configuration’s work tapes unchanged, each visited-span marker covers the corresponding current source head, and each origin tape carries its single marker.
The configuration of the tracked evaluator between the two microsteps of a round: the source data, input position, heads, and emitted output already reflect the source action, while the visited-interval markers are still the previous ones.
For a live source configuration \(c\), one step of the tracked evaluator from the tracked configuration of \(c\) yields the intermediate stamp configuration of the source configuration after one source step: the data simulation is exact (including any halting emission), and both marker heads move with the data head without writing.
Suppose each visited span \([\mathrm{lo}_i, \mathrm{hi}_i]\) is nonempty and each current source head lies within one cell of it. Then one step of the tracked evaluator from the intermediate stamp configuration marks every current head cell, producing the tracked configuration whose spans are extended to \([\min (\mathrm{lo}_i, h_i), \max (\mathrm{hi}_i, h_i)]\), and only then dispatches the stored successor state.
For a machine \(M\), an input \(x\), and a work tape, the leftmost visited position at time \(0\) is \(0\), and at time \(t+1\) it is the minimum of its value at time \(t\) and the position of that work head after \(t+1\) steps of \(M\) on \(x\).
For a machine \(M\), an input \(x\), and a work tape, the rightmost visited position at time \(0\) is \(0\), and at time \(t+1\) it is the maximum of its value at time \(t\) and the position of that work head after \(t+1\) steps of \(M\) on \(x\).
For every time \(t\) and work tape \(i\), the visited interval \([\mathrm{lo}, \mathrm{hi}]\) of the run contains \(0\) and the current head position, and satisfies \(-t \le \mathrm{lo}\) and \(\mathrm{hi} \le t\); in particular its width is at most \(2t + 1\).
At every time \(t\), every work-tape cell lying outside the visited interval of its tape is blank; blank cells inside the interval are permitted.
The closed visited span from \(0\) to \(0\) equals the tape holding the single-cell marker word.
For every machine \(M\) and input \(x\), one step of the tracked evaluator for \(M\) from its initial configuration on \(x\) yields the tracked configuration of the initial configuration of \(M\) on \(x\) with every visited span equal to \([0, 0]\): both origin markers are installed, the source work tapes are blank, and the output is empty.
For every time \(t\), the tracked evaluator’s configuration after \(1 + 2t\) native steps is exactly the tracked configuration of the source machine’s configuration after \(t\) steps, with visited intervals given by the leftmost and rightmost visited positions through time \(t\); this holds also after the source has halted.
If a machine halts on input \(x\) with output \(o\) within \(T\) steps, then its tracked evaluator halts on \(x\) with the same output \(o\) within \(1 + 2T\) steps.
For \(\mathrm{lo} \le \mathrm{hi}\), the closed visited span \([\mathrm{lo}, \mathrm{hi}]\) equals the cleaner’s half-open interval marker with left endpoint \(\mathrm{lo}\) and width \(\mathrm{hi} - \mathrm{lo} + 1\).
For each work tape of a source machine run for \(T\) steps, there is a time \(t\) with \(0 \lt t \le 6T + 7\) after which the interval cleaner, started on that tape’s data together with its tracked visited span and origin marker at the tape’s current head position, reaches its return state with all three tapes blank and all heads at the origin.
Let a class of control states be absorbing (any configuration whose state lies in the class is a fixed point of the step function), and suppose the run from \(c\) reaches a configuration \(d\) with state in the class after \(T\) steps. Then there is a time \(t \le T\) with no earlier visit to the class such that the configuration at time \(t\) is already \(d\).
For words \(u, v\), there is a time \(t\) with \(0 \lt t \le 2(\max (\left\lvert u\right\rvert ,\left\lvert v\right\rvert ) + 1)\) such that the comparator never visits either Boolean return state before time \(t\) and at time \(t\) sits in its return configuration with the register recording whether \(u = v\) and both heads at zero.
For each work tape of a source machine run for \(T\) steps, there is a time \(t\) with \(0 \lt t \le 6T + 7\) such that the interval cleaner, started on that tape’s data with its tracked span and origin marker, never visits its return state before time \(t\) and at time \(t\) has reached the all-blank return configuration.
The map sending a natural number to its little-endian binary representation is injective: distinct natural numbers have distinct binary digit words.
For a work-tape index \(i\), the bank-triple projection sends a symbol vector over the tracked three-bank layout to the triple of its data, visited-marker, and origin-marker symbols at index \(i\).
The action performed by one component of the simultaneous cleanup: a live component takes its interval cleaner’s transition on its own triple of symbols, and a stopped component performs the stationary silent action; the native input is ignored.
The machine running \(k\) interval cleaners simultaneously on disjoint data/marker/origin triples: its finite control stores the vector of all component cleaner states, and no source-time clock is present.
Given \(k\) interval-cleaner configurations on a physical input \(w\) and an input-head position \(p\), the assembled bank configuration is the configuration of the simultaneous cleaner bank whose control state is the vector of the \(k\) cleaner states, whose data, visited-marker, and origin-marker banks carry the corresponding tapes and head positions of the \(k\) cleaners, whose input head is at \(p\), and whose physical output is empty.
Selecting component \(i\) of the assembled bank configuration recovers exactly the \(i\)-th cleaner’s transition on its own configuration, including all three independently positioned work heads; a halted component yields the stationary action.
One step of the simultaneous cleaner bank from an assembled configuration equals the assembly of one step of every component cleaner; the physical input and output are preserved.
For every time \(t\), the simultaneous cleaner bank’s run from an assembled configuration equals the assembly of each component cleaner’s \(t\)-step run.
Any configuration of the interval cleaner in its return state is a fixed point of the step function: every field is preserved by further steps.
After a source machine has run for \(T\) steps, exactly \(6T + 7\) steps of the simultaneous cleaner bank, started on the assembly of all tracked tapes with their spans and origin markers, clear the entire bank: all data, marker, and origin tapes become blank with every work head at zero, while the physical input head and output are unchanged; this includes a source with no work tapes.
Any configuration of the simultaneous cleaner bank whose every component is in its return state is a fixed point of the step function: no tape, head, or control field changes on further steps.
After a source machine has run for \(T\) steps, there is a time \(t \le 6T + 7\) such that the simultaneous cleaner bank, started on the assembly of all tracked tapes, never shows the all-returned state vector before time \(t\) and at time \(t\) has reached the fully blank assembled endpoint; a bank over zero tapes may return at time zero.
Given a machine \(M\), the right-boundary wrapper is the machine that simulates \(M\) exactly and, after the actual halt of \(M\), moves the input head to the right input boundary without altering the output or work tapes of \(M\); the initial positive move of the scan handles the two distinct blanks of an empty input correctly.
The right-boundary wrapper’s configuration corresponding to a source configuration: all fields are preserved, with a halted source state replaced by a live administrative state.
For a live source configuration \(c\), one step of the right-boundary wrapper from the wrapper configuration of \(c\) equals the wrapper configuration of the source configuration after one step, including any halting emission; only the control-state encoding differs.
If the source stays live for all times before \(t\), then \(t\) steps of the right-boundary wrapper from the wrapper configuration of \(c\) equal the wrapper configuration of the source run at time \(t\).
A configuration of the right-boundary wrapper during its final scan: the completed source’s work tapes and output are carried verbatim, and only the physical input position varies.
Let \(x\) be an input and let \(c\) be a source configuration on \(x\). For all \(j\) and \(r\) with \(j + r = \left\lvert x\right\rvert \), exactly \(r + 1\) silent steps of the right-boundary wrapper from the scan configuration of \(c\) at position \(j\) reach the halted scan configuration of \(c\) at position \(\left\lvert x\right\rvert \); the scan never mistakes a blank work cell for the end of the input.
For a halted source configuration \(c\), there is a time \(t \le \left\lvert x\right\rvert + 2\) after which the right-boundary wrapper, started from the wrapper configuration of \(c\), has reached the halted scan configuration at the right boundary; neither the mandatory initial positive move nor the scan changes the completed work tapes or output.
If a source machine has halted on input \(x\) by time \(T\), then \(T + \left\lvert x\right\rvert + 2\) steps of its right-boundary wrapper from the initial configuration reach the halted scan configuration carrying the complete source configuration at time \(T\) — work tapes included — with the input head at the right boundary.
If a machine halts on input \(x\) with output \(o\) within \(T\) steps, then its right-boundary wrapper halts on \(x\) with output \(o\) within \(T + \left\lvert x\right\rvert + 2\) steps, and at that time its input head sits at position \(\left\lvert x\right\rvert + 1\).
Let \(M\), on the candidate \(s\), halt within \(T\) steps with output \(o\), and let the composite evaluator capture the tracked, right-normalized simulation of \(M\). Then there is a time \(t\) with \(0 \lt t \le 1 + 2T + \left\lvert s\right\rvert + 2\) such that the composite never visits its return state before \(t\) and at time \(t\) sits in the evaluator configuration carrying the full tracked trace banks, the complete captured output, the candidate head at the right boundary, nothing on the physical output, and the physical input head fixed at position one.
For a candidate \(s\) with \(\left\lvert s\right\rvert \le \left\lvert w\right\rvert \), the binary representation of \(f(\left\lvert s\right\rvert )\) equals the binary representation of the length of the suffix of \(w\) after position \(\left\lvert s\right\rvert \) if and only if \(\left\lvert s\right\rvert + f(\left\lvert s\right\rvert ) = \left\lvert w\right\rvert \); this includes the case of two empty words.
Let a machine \(E\) compute the binary width word \(s \mapsto \mathrm{bits}(f(\left\lvert s\right\rvert ))\) within a monotone time bound \(T_E\). Then for any candidate \(s\) of length at most \(\left\lvert w\right\rvert +1\): \(E\) halts on \(s\) with that output within \(T_E(\left\lvert s\right\rvert )\) steps, the output’s length is at most \(T_E(\left\lvert s\right\rvert )\), and \(T_E(\left\lvert s\right\rvert ) \le T_E(\left\lvert w\right\rvert +1)\).
Let a machine compute the binary width word within a monotone bound \(T_E\), and let the candidate \(s\) have length at most \(\left\lvert w\right\rvert + 1\). Then the composite evaluator has a first return at some positive time \(t \le 3(T_E(\left\lvert w\right\rvert +1) + \left\lvert w\right\rvert + 2)\), at which it retains its tracked work banks and the exact captured width word.
The transform relocating an action of a \(k\)-tape machine to an arbitrary fixed set of slots among \(l\) host tapes, specified by a partial selection map: selected tapes perform the original writes and moves, and every unselected tape is stationary.
The host configuration embedding a \(k\)-tape configuration into \(l\) host tapes via a selection map: selected slots carry the source tapes and heads, unselected slots keep given contents and head positions, and the output is the source’s physical output.
Applying a relocated action to a relocated configuration equals relocating the result of applying the original action: the write, head motion, and emission are reproduced on the selected slots, and unselected tape contents and positions are fixed.
Let the host’s transitions on embedded good states equal the relocated source transitions, with the selection map a left inverse of the tape indexing. If every state visited by the source before time \(t\) is good, then \(t\) host steps from the relocated configuration equal the relocation of the source’s \(t\)-step run.
A three-state, one-work-tape machine that erases one contiguous administrative word: it scans the word to its right blank, erases it right to left, and crosses the left blank once to restore the head to the origin, stalling in an absorbing return state; blanks may serve as word boundaries because the word is complete and canonical.
Given a physical input \(w\), a word \(u\), a control state \(q\), and a displacement \(h\), the eraser configuration is the configuration of the administrative-word eraser in state \(q\) with \(u\) on its single tape, its head at displacement \(h\), the physical input head on the first input cell, and empty output.
For every \(j \le \left\lvert u\right\rvert \), \(j\) steps of the eraser from the start of the intact word \(u\) move its head to displacement \(j\), preserving the word and emitting nothing.
From the eraser’s backward state with the word \(u\) and head at displacement \(\left\lvert u\right\rvert - 1\), exactly \(\left\lvert u\right\rvert + 1\) steps erase every cell of \(u\) right to left and restore the head to the origin, reaching the return state with a blank tape.
Erasing a complete administrative word \(u\) costs exactly \(2(\left\lvert u\right\rvert +1)\) steps of the eraser, after which the tape is blank, the head and native input position are restored, and nothing has been emitted.
For any word \(u\), there is a time \(t\) with \(0 \lt t \le 2(\left\lvert u\right\rvert +1)\) such that the eraser never visits its return state before \(t\) and at time \(t\) has reached the blank-tape return configuration; the return is positive even for the empty word.
A three-tape machine with nine control phases that prepares the arguments of the width evaluation: it copies the candidate from its first tape onto a fresh second tape while advancing the native input head with saturation, copies the remaining native suffix onto a fresh third tape, rewinds all work heads along the preserved words and then rewinds the native input; a finite flag records only whether the candidate ran past the native right boundary.
A configuration of the candidate-and-suffix preparation machine: the three tapes hold the candidate, its copy, and the scanned native suffix, with the candidate and copy heads aligned, a separate suffix head, a control phase with overflow flag, and a given native input position.
For every \(j \le \left\lvert s\right\rvert \), \(j\) steps of the preparation machine from its start copy the first \(j\) bits of the candidate \(s\) onto the second tape, advance the native head to its saturated position for \(j\), and set the overflow flag exactly when \(\left\lvert w\right\rvert \lt j\); the candidate itself never changes.
For every \(j\) at most the length of the native suffix after position \(\left\lvert s\right\rvert \), \(j\) steps of the preparation machine in its suffix phase copy the first \(j\) bits of that suffix onto the third tape and advance the native head accordingly; the other tapes are unchanged.
From the preparation machine’s candidate-rewind phase with the aligned candidate and copy heads at displacement \(j - 1\), for any \(j \le \left\lvert s\right\rvert \), exactly \(j+1\) steps restore both heads to the origin without changing either word; the native input position and the prepared suffix are fixed.
Let \(j\) be at most the length of the suffix word. From the preparation machine’s suffix-rewind phase with the suffix head at displacement \(j - 1\), exactly \(j+1\) steps yield the frame of the next phase with the suffix head at the origin; all three words are preserved.
If the run from \(c\) reaches \(d\) in exactly \(a\) steps and the run from \(d\) reaches \(e\) in exactly \(b\) steps, then the run from \(c\) reaches \(e\) in exactly \(a + b\) steps.
For any input \(w\) and candidate \(s\), there is a time \(t \le 5(\left\lvert s\right\rvert + \left\lvert w\right\rvert + 3)\) after which the candidate-and-suffix preparation machine, started from its initial frame, presents the candidate \(s\) and the native suffix of \(w\) after position \(\left\lvert s\right\rvert \) on clean argument tapes, with every head and the native input position restored and the overflow flag recording whether \(\left\lvert w\right\rvert \lt \left\lvert s\right\rvert \).
For any input \(w\) and candidate \(s\), there is a time \(t\) with \(0 \lt t \le 5(\left\lvert s\right\rvert + \left\lvert w\right\rvert + 3)\) such that the preparation machine never visits its return phase before \(t\) and at time \(t\) sits in its completed frame with the candidate and native suffix prepared; positivity holds even for empty input and an empty candidate.
Under the relocation hypotheses — the selection map inverts the tape indexing, no embedded state equals the host anchor, and host transitions on embedded good states equal the relocated source transitions — an exact source run from \(c\) to \(d\) in \(t\) steps, all of whose visited states are good, relocates to an exact host run between the relocated configurations whose whole trace avoids the anchor.
Let a host enter a relocated module through a dedicated entry control state that performs the module entry state’s action unconditionally, and agree with the relocated module transitions away from the module’s exit state. If the module runs from its entry configuration to \(d\) in \(t \gt 0\) steps with no interior visit to the exit state, then \(t\) host steps from the entry configuration land on the relocation of \(d\), with the whole trace avoiding the host anchor; this covers modules whose entry and exit states coincide.
The layout of stored words across the \(k + l + 1\) host tapes: the preserved candidate first, then the width-call bank of \(k\) tapes, then the suffix-length-call bank of \(l\) tapes; at a seam only the first tape of each bank carries a word and all other tapes are blank.
For all bank sizes \(k\) and \(l\), the width-bank injection sends tape \(i\) of the width-call machine (with \(i \lt k\)) to host position \(i + 1\), immediately after the preserved candidate tape at position \(0\).
The partial selection map recognizing exactly the width-call bank among the host tapes.
For all bank sizes \(k\) and \(l\), the length-bank injection sends tape \(i\) of the suffix-length-call machine (with \(i \lt l\)) to host position \(k + i + 1\), immediately after the width-call bank.
The partial selection map recognizing exactly the suffix-length-call bank among the host tapes.
Selecting the host slot at the width-bank injection of index \(i\) returns exactly \(i\).
Selecting the host slot at the length-bank injection of index \(i\) returns exactly \(i\).
Relocating a canonical state-word configuration of the width-call machine into the host layout — with the candidate and suffix words preserved on their ambient tapes — yields exactly the host’s canonical configuration on the full word layout with the width word installed.
Relocating a canonical state-word configuration of the suffix-length-call machine into the host layout — with the candidate and width words preserved — yields exactly the host’s canonical configuration on the full word layout with the length word installed.
With both argument words erased, the host word layout for candidate \(s\) equals the loop’s canonical state word on \(k + l + 1\) tapes carrying \(s\), including every inactive tape.
The partial selection map recognizing one designated physical tape, so that a one-tape phase relocated through it leaves every other tape fixed.
Selecting the designated slot through the single-tape selection map returns the unique one-tape index.
For a host slot, a host word layout, a physical input \(w\), a word \(u\), and a state \(q\), relocating the canonical one-word configuration of a single-tape phase (state \(q\), word \(u\)) into that slot, with every other tape holding its layout word at head position \(0\), yields the canonical host configuration whose layout equals the given layout with the slot’s word replaced by \(u\).
For all positive bank sizes \(k\) and \(l\), the administrative-triple injection sends index \(0\) to the candidate position \(0\), index \(1\) to host position \(1\) (the first width-bank tape), and index \(2\) to host position \(k + 1\) (the first length-bank tape).
The partial selection map recognizing the three administrative word slots — candidate, width word, and length word — and leaving all module scratch tapes inactive.
For positive bank sizes, selecting the host slot at the administrative-triple injection of any of the three indices returns that index.
At zero head displacements, relocating a preparation frame through the administrative-triple selection coincides exactly with the host’s canonical configuration on the complete word layout, not merely with its two argument projections.
The injection sending the comparator’s two tapes to the first tapes of the two call banks, which hold the two words to be compared.
The partial selection map recognizing the two comparison word slots while keeping the candidate and all scratch tapes fixed.
For positive bank sizes, selecting the host slot at the comparator-pair injection of either index returns that index.
Relocating a comparator configuration at zero displacement through the comparator-pair selection yields the host’s canonical configuration whose layout holds the two whole compared words together with the unchanged candidate, every module scratch tape being blank.
Replacing the word at the first width-bank slot of the host layout for \((s, u, v)\) by a word \(a\) yields exactly the layout for \((s, a, v)\); every other slot is untouched.
Replacing the word at the first length-bank slot of the host layout for \((s, u, v)\) by a word \(a\) yields exactly the layout for \((s, u, a)\); the candidate and width words are preserved.
For all words \(s\), \(u\), \(v\), and \(a\), replacing the word at the candidate slot of the host layout for \((s, u, v)\) by \(a\) yields exactly the layout for \((a, u, v)\).
Given state types \(S\) and \(T\) of the width and length call machines, the controller-phase type of the width-split round has an anchor, a preparation phase, dedicated start states and running phases (carrying a state of \(S\), respectively \(T\)) for the width call and the suffix-length call, a comparison phase, two erasure phases carrying the verdict, an advance (cleanup) phase, and an emission phase.
Given clean-call machines \(C\) (width evaluator) and \(D\) (suffix-length evaluator) with designated entry and exit states, the native controller of one width-split round: it prepares the candidate copy and native suffix, runs the two relocated calls on their disjoint banks, compares the two returned words whole-word, erases both result words while carrying the verdict, and then either emits the native split or advances the candidate and returns to the anchor; a past-the-end preparation bypasses both evaluators, the native input is never overwritten, and no time bound or width function appears in the transition table.
On every input \(w\), the width-split controller’s initial configuration equals the canonical anchored configuration whose stored words carry the empty candidate.
If a control state’s transition is the unconditional silent dispatch to a state \(r\), then one step from the canonical word-seam configuration in that state yields the canonical word-seam configuration in state \(r\) with every other component unchanged.
For any input \(w\) and candidate \(s\), there is a time \(t \le 5(\left\lvert s\right\rvert + \left\lvert w\right\rvert + 3)\) such that the controller, from its preparation seam carrying \(s\), reaches the seam holding the candidate, its copy, and the native suffix of \(w\) after position \(\left\lvert s\right\rvert \), with the past-the-end flag recording \(\left\lvert w\right\rvert \lt \left\lvert s\right\rvert \); the trace avoids the anchor.
If the width machine, started on its canonical seam carrying the candidate copy, reaches its exit seam with result word \(u\) in \(t \gt 0\) steps with no interior exit-state visit, then \(t\) controller steps from the width-start seam install \(u\) in the width bank while retaining the original candidate and prepared suffix; the trace avoids the anchor.
If the suffix-length machine, started on its canonical seam carrying the prepared suffix, reaches its exit seam with result word \(z\) in \(t \gt 0\) steps with no interior exit-state visit, then \(t\) controller steps from the length-start seam install \(z\) in the length bank while preserving the candidate and the already installed width word; the trace avoids the anchor.
For installed result words \(u\) and \(v\), there is a time \(t \le 2(\max (\left\lvert u\right\rvert ,\left\lvert v\right\rvert ) + 1)\) after which the controller, from its comparison seam, records in finite control whether \(u = v\), changing no candidate, buffer, or module scratch cell; the trace avoids the anchor.
For any verdict bit, there is a time \(t \le 2(\left\lvert u\right\rvert +1)\) after which the controller, from its first erasure seam, has blanked the installed width word \(u\) while retaining the verdict in control and preserving every other tape; the trace avoids the anchor.
For any verdict bit, there is a time \(t \le 2(\left\lvert v\right\rvert +1)\) after which the controller, from its second erasure seam, has blanked the installed length word \(v\) while retaining the verdict through the last cleanup phase; after this all scratch and administrative words are blank. The trace avoids the anchor.
The one-tape candidate-advance machine’s starting scan configuration equals the canonical word-seam configuration carrying the candidate on its single tape.
The canonical state word on one tape carrying \(s\) is the constant function with value \(s\).
There is a time \(t \le 2\left\lvert s\right\rvert + \left\lvert w\right\rvert + 5\) after which the controller, from its advance seam carrying the candidate \(s\), has replaced \(s\) by one split-search step applied to \(s\) (appending a \(1\) exactly within the input range, and stalling otherwise) and reached the advance phase’s return seam; the trace avoids the anchor.
The one-tape payload emitter’s starting configuration equals the canonical word-seam configuration carrying the candidate on its single tape.
If the candidate’s length is at most \(\left\lvert w\right\rvert \), then exactly \(\left\lvert s\right\rvert + \left\lvert w\right\rvert + 3\) controller steps from the emission seam halt with output the self-delimiting pair encoding of the split of the native input \(w\) at position \(\left\lvert s\right\rvert \); the emitted bits come from the native input, not the candidate, unrelated banks stay blank, and the trace avoids the anchor.
If an anchor-free run of length \(t\) ends on a canonical word seam in a non-anchor state whose transition is the silent dispatch to another non-anchor state, then the run of length \(t+1\) ends on the same word seam in the new state and is still anchor-free.
Suppose the width call completes in \(a \gt 0\) steps with result \(u\) and the suffix-length call completes in \(b \gt 0\) steps with result \(v\), each with no interior exit-state visit. Then there is a time \(t \le a + b + 2(\max (\left\lvert u\right\rvert ,\left\lvert v\right\rvert ) + 1) + 4\) after which the controller, from its completed-preparation seam, has run both calls and the whole-word comparison and sits at the first erasure seam carrying the verdict of \(u = v\); both calls are charged before any relation between their results is assumed, and the trace avoids the anchor.
Let a verdict bit be given, true only if the candidate’s length is at most \(\left\lvert w\right\rvert \). Then there is a time \(t \le 2\left\lvert u\right\rvert + 2\left\lvert v\right\rvert + 2\left\lvert s\right\rvert + \left\lvert w\right\rvert + 12\) after which the controller, from the first erasure seam, has erased both installed words and: on a true verdict, halted with output the pair encoding of the split of \(w\) at position \(\left\lvert s\right\rvert \); on a false verdict, returned to the canonical anchored seam carrying one split-search step applied to \(s\). No strictly interior configuration is at the anchor.
If the run from \(c\) reaches \(d\) in \(a\) anchor-free steps and the run from \(d\) avoids the anchor at all times strictly before \(b\), then the run from \(c\) avoids the anchor at all times strictly before \(a + b\), even when time \(a + b\) itself returns to the anchor.
Suppose the width call on the candidate \(s\) returns the binary word of \(f(\left\lvert s\right\rvert )\) in \(a \gt 0\) steps and the suffix-length call returns the binary word of the suffix length in \(b \gt 0\) steps, each with no interior exit-state visit. Then there is a time \(t\) with \(0 \lt t \le a + b + 10(\left\lvert s\right\rvert + \left\lvert w\right\rvert + \ell _u + \ell _v + 10)\), where \(\ell _u, \ell _v\) are the two binary words’ lengths, such that the round from the canonical anchored seam carrying \(s\) never revisits the anchor strictly between \(0\) and \(t\), and at time \(t\): if \(\left\lvert s\right\rvert + f(\left\lvert s\right\rvert ) = \left\lvert w\right\rvert \) the controller has halted with output the pair encoding of the split of \(w\) at \(\left\lvert s\right\rvert \), and otherwise it is back at the canonical anchored seam carrying the stepped candidate.
Let a machine \(E\) compute the binary representation of \(f\) applied to the input length within a monotone time bound \(T_E\). Then there exist a machine \(M\) and a constant \(c\) computing, within \(c\, (n+1)(T_E(n+1) + n + 2)\) steps, the function sending \(w\) to the pair encoding of the split of \(w\) at the least \(i\) with \(i + f(i) = \left\lvert w\right\rvert \), and to the empty word when no such \(i\) exists.
Let \(f : \mathbb {N} \to \mathbb {N}\) and let a machine \(E\) compute the function sending an input of length \(m\) to the little-endian binary representation of \(f(m)\) within a monotone time bound \(T_E\). Then there exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes, within \(c\, (n+1)(T_E(n+1) + n + 2)\) steps on inputs of length \(n\), the function that on input \(w\) finds the least \(i \le \left\lvert w\right\rvert \) with \(i + f(i) = \left\lvert w\right\rvert \) and, on success, outputs the self-delimiting pair encoding of the first \(i\) bits of \(w\) paired with the rest of \(w\), and on failure outputs the empty word.
A six-state machine without work tapes that splits off its input’s leading unary token in one streaming pass: each token bit is emitted doubled, the token’s terminating \(0\) is followed by the separator bits \(0,1\), and the remainder is copied verbatim; a right blank during token scanning starts the separator directly, so an unterminated token and the empty input are both retained.
If the input splits as \(x = p\, b\, r\) with bit \(b\), two transitions of the token encoder from its scanning state at position \(\left\lvert p\right\rvert \) emit \(b\) twice and advance the input head once; the encoder continues token scanning when \(b = 1\) and passes to the separator phase when \(b = 0\).
For every input \(x\), position \(i \le \left\lvert x\right\rvert \), and prior output \(o\), two transitions of the token encoder from its separator phase at position \(i\) yield the suffix-copying state at the same position \(i\), with output \(o\) followed by the pair delimiter bits \(0,1\).
Let the unconsumed input \(r\) split at its leading unary token into the token \(a\) (the maximal leading run of ones with its terminating zero, if present) and the remainder \(b\). Then, after any consumed prefix and prior output \(o\), exactly \(2\left\lvert a\right\rvert + \left\lvert b\right\rvert + 3\) steps of the token encoder halt with output \(o\) followed by the self-delimiting pair encoding of \((a, b)\), the final step being the blank-reading halt.
For every word \(x\), the length of the leading unary token of \(x\) plus the length of the remainder equals \(\left\lvert x\right\rvert \); this includes the empty input and an unterminated token.
There exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes, within \(c\, (n+1)\) steps on inputs of length \(n\), the function splitting its input at the leading unary token — the maximal leading run of ones with its terminating zero, if present — and emitting the self-delimiting pair encoding of the token and the remainder.
For a fixed bit \(b\), the bit-appending machine is the single-state machine without work tapes that copies each input bit to the output and emits \(b\) on the right-blank halting transition.
For every \(j \le \left\lvert x\right\rvert \), after \(j\) steps from its initial configuration on input \(x\) the bit appender is at input position \(j\) with output exactly the first \(j\) bits of \(x\); the appending halt is still ahead.
For every fixed bit \(b\) there exist a finite Turing machine \(M\) and a constant \(c\) such that \(M\) computes the function \(x \mapsto x b\) (append the bit \(b\) to the input word) within \(c\, (n+1)\) steps on inputs of length \(n\).