Circuit Optimization, Resource Tradeoffs, and Lower Bounds

Two-word addition has the following constant-depth Boolean construction. For $d$-bit words $a,b$, put $g_j=a_j\wedge b_j$ and $p_j=a_j\vee b_j$. The carry entering bit $k>0$ is $c_k={\bigvee }_{0\le j<k}(g_j\wedge {\bigwedge }_{j<t<k}{p}_t),c_0=0.$ A carry is generated by two ones, propagated through positions with at least one one, and killed by two zeros; this proves the formula. The output bit is the XOR of $a_k,b_k,c_k$, computed by its constant-size Boolean truth table, with the final carry appended. These formulas have constant depth and polynomial size, and predecessor tests use equality and order on their bit-position addresses.

For $m\ge 2$, let $\mathrm{\ell }=\lceil {\log }_{2}m\rceil$, let $b$ be the least power of two at least $\mathrm{\ell }$, and put $B=2^b$. Then $m\le B\le m^2$. Split each input into consecutive $b$-bit blocks and pad the last block with zeros. For block $q$, define $S_q={\sum }_{i=0}^{m-1}{\sum }_{r=0}^{b-1}{2}^r{x}_{i,qb+r}\mathrm{.}$ Its upper bound is $C=m(B-1)$, polynomial in $mw$.

To compute all bits of $S_q$, pad the row domain to a power of two $M_0\ge m$ with $M_0<2m$. Create a rectangular set of distinct copy gates $(i,r,t)$ with $0\le i<M_0$, $0\le r<b$, and $0\le t<B$. Gates with $i\ge m$ or $t\ge 2^r$ are zero; otherwise they copy $x_{i,qb+r}$. There are $D=M_{0}bB$ slots, a power of two polynomial in $mw$, and exactly $S_q$ slots are true. For each $1\le h\le D$, feed these slots and $D+1$ distinct constant slots to a MAJ gate, with exactly $D-h+1$ constant slots equal to one. Its odd fan-in is $2D+1$, so under either convention for majority it tests $S_q+(D-h+1)\ge D+1$, equivalently $S_q\ge h$. Write this output as $T_{q,h}$ and set $T_{q,0}=1$, $T_{q,D+1}=0$. Then $E_{q,h}=T_{q,h}\wedge \mathrm{\neg }{T}_{q,h+1}$ tests $S_q=h$, and bit $u$ of $S_q$ is the OR of $E_{q,h}$ over the indices $h$ having bit $u$ equal to one. The depth is constant and the size polynomial.

Write $S_q=r_q+B{v}_q$. Since $r_q<B$ and $v_q<m\le B$, form two words: $R$ has block $q$ equal to $r_q$, and $V$ has block $q+1$ equal to $v_q$ and block zero zero. These bits are direct selections from the bits computed in step 2.1. The blocks do not overlap within either word, and ${\sum }_{i=0}^{m-1}{x}_i={\sum }_q{S}_q{B}^q=R+V\mathrm{.}$ Apply step 1.1 once to $R,V$. This is a constant number of constant-depth stages of polynomial total size.

We verify uniformity explicitly. Use fixed-length tuples with a constant number of $O(\log (mw+2))$-bit fields for gate type, block, row, within-block bit, copy, threshold, output-bit and constant-slot indices. All predecessor predicates in step 1.1 and step 1.2 and step 2.1 and step 3.1 use equality, order, the bit predicate on $h$, $t<2^r$, the constant-slot test $u<D-h+1$, and $j=qb+r$. Since $b$ is a power of two, the last relation is a shift and concatenation. The exponent of the power of two $D=M_{0}bB$ is the sum of the corresponding bit-length exponents. Testing $t<2^r$ compares $r$ with the highest nonzero bit position of $t$. Determine the field widths and $b$ from the binary dimensions and perform these tests by a constant number of linear scans, additions, subtractions, shifts and comparisons of $O(\log (mw+2))$-bit words. Each gate-type or predecessor query takes $O(\log (mw+2))$ time on the random-access uniformity machine; no general multiplication of two varying address fields is used. Dimensions and coordinate domains are padded to powers of two, and positions outside the actual input bounds are constant zero. For $m=1$, copy the input word. Finally ${\sum }_i{x}_i<m{2}^w\le 2^{w+\lceil {\log }_{2}m\rceil }$, so the retained output width is exactly the one in the Statement.

A function of a fixed number of short arguments has polynomially many argument tuples. If its table is logspace-computable, realize each output bit by an OR of equality conjunctions over the tuples yielding one. This is a constant-depth polynomial-size logspace-uniform Boolean lookup circuit. Short addition, multiplication, reduction, inverses modulo a prime, and the table $(a,e,p)\mapsto a^e<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>p$ have this property. For the power table, use repeated squaring with a constant number of short residues and a short exponent counter; short multiplication uses grade-school arithmetic in logarithmic space. Find an inverse by trying every short candidate, and test primality by trial division. Enumerate the $j$-th prime by a counter and these primality tests whenever $j$ and that prime are polynomially bounded. We may also add polynomially many polynomial-width words by [F3], whose uniformity is stronger than required here.

For a fixed short prime $p>2$, [F2] gives a generator $g$ of the nonzero residues. Find the least such $g$ by testing all candidates and all exponents below $p-1$ with step 1.1. The tables $a\mapsto \mathrm{\ell }(a)$, where $g^{\mathrm{\ell }(a)}\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$ and $0\le \mathrm{\ell }(a)<p-1$, and $(g,e,p)\mapsto g^e<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>p$ are logspace-computable by enumeration and modular powering with a constant number of short counters. For nonzero inputs $a_1,\dots ,a_d$ with polynomially bounded $d$, their product modulo $p$ is $g^{{\sum }_i\mathrm{\ell }(a_i)}<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>p$. The exponent sum is polynomially bounded, so compute it with [F3] and use a short power lookup. If any input is zero, select zero instead. For $p=2$, the product is one exactly when all inputs are one. This gives iterated multiplication in any fixed polynomial-size residue basis in logspace-uniform constant depth. It uses only short tables and addition, without assuming binary iterated multiplication.

Convert a long word $X={\sum }_j{x}_j{2}^j$ to residues by computing $x_j(2^j<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>p)$ for each bit position and modulus, summing these short contributions with [F3], and reducing the result modulo $p$ by step 1.1. The sum is polynomially bounded in $N$, because its number of contributions and $p$ are. Each constant $2^j<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>p$ is logspace-computable. Thus binary-to-residue conversion has the required circuit bounds; for $X$ outside the basis range, its vector represents its remainder in that range.

Fix a basis $T={\prod }_{i=1}^k{p}_i$ of distinct short primes. Set $C_i=T\mathrm{/}{p}_i$ and $h_i=(C_i<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>p_i{)}^{-1}<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>p_i$. The binary words $T,C_i$ need not be computed: their required short residues, and then $h_i$, are generated in logspace by scanning factors and multiplying modulo $p_i$. Since $C_i{h}_i$ is one modulo $p_i$ and zero modulo all other basis primes, for the residue vector $(x_i)$ of $0\le X<T$ we have ${\sum }_i{x}_i{h}_i{C}_i=X+rT,S:={\sum }_i\frac{x_i{h}_i}{p_i}=r+\frac{X}{T}$ for a nonnegative integer $r$. Indeed a difference divisible by each of the distinct primes is divisible by their product, while two representatives in $[0,T)$ cannot differ by a nonzero multiple of $T$. Existence of a representative for every residue vector follows by taking the remainder modulo $T$ of the displayed nonnegative sum.

We give a comparison circuit with controlled rounding. Let $U$ bound the primes of the fixed basis, put $L=k\lceil {\log }_{2}U\rceil$, so $T\le 2^L$, and choose $t=L+\lceil {\log }_{2}k\rceil +4$. Compute $F_i=\lfloor x_i{h}_i{2}^t\mathrm{/}{p}_i\rfloor$ and $Z=\frac{{\sum }_i{F}_i+k}{2^t},S\le Z\le S+\epsilon ,\epsilon =k{2}^{-t}<\frac{1}{4T}\mathrm{.}$ Because $X\mathrm{/}T$ is a multiple of $1\mathrm{/}T$ in $[0,1)$, $\lfloor Z\rfloor =r$, including $X=0$ and $X=T-1$. The low $t$ bits of ${\sum }_i{F}_i+k$ therefore represent a dyadic fraction $f_X$ satisfying $X\mathrm{/}T\le f_X\le X\mathrm{/}T+\epsilon$. Hence $X<Y$ if and only if $f_X<f_Y$: distinct representatives differ by at least $1\mathrm{/}T$, and equal representatives give identical residue vectors and identical fractions. All bits of $F_i$ have the required circuits. Its integer part $\lfloor x_i{h}_i\mathrm{/}{p}_i\rfloor$ is a short lookup. For odd $p_i$, bit $j\ge 1$ after the binary point of $x_i{h}_i\mathrm{/}{p}_i$ equals $(x_i{h}_i{2}^j<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>p_i)<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>2$: write $x_i{h}_i{2}^j=a{p}_i+b$; its even left side and odd $p_i$ imply that $a,b$ have the same parity. These residues are short lookups using modular-power constants. For $p_i=2$, only the first fractional bit can be nonzero. This computes precisely the truncation defining $F_i$. Sum with [F3] and compare the $t$-bit fractions by an OR over their highest differing position, with equality required at all higher positions. That comparator is constant-depth Boolean. Thus residue comparison is logspace-uniform constant depth. The upward offset is essential to handle an exact integer $S$ correctly.

Put $k=N+5$ and let $M$ be the product of the first $k$ primes, including $2$. Then $M\ge 2^k>2^{N+4}$. For each output index $1\le s<N$, take $s$ disjoint blocks of $k$ consecutive primes beyond those first $k$ primes, and let $A_i$ be the product of block $i$. Every $A_i$ is odd and exceeds $M$, since each of its factors exceeds the corresponding factor of $M$. The $A_i$ are pairwise relatively prime and relatively prime to $M$. Only $O(N^2)$ primes are needed. By [F1], their numerical values are polynomially bounded in $N$ for all sufficiently large $N$; the finitely many smaller dimensions have fixed circuits. Enumeration of each block and its residues modulo any short prime is logspace-computable by scanning its factors as in step 1.1 and step 2.3. No bit of a long prime product is requested from the uniformity machine.

Extend the representation of $X\in [0,T)$ to a fixed short prime $q$ not in its basis by trying every possible residue $a\in [0,q)$. In basis $Tq$, each candidate has a unique representative $X_a$. The representatives with the old residues are exactly $X+jT$, $0\le j<q$, so exactly one is below $T$. The representation of $T$ in basis $Tq$ has zero on the old primes and the fixed short product $T<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>q$ on the new prime. Compare each candidate with it using step 3.1 and select the unique successful $a$. This computes $X<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>q$. Extend to any polynomial-size new basis in parallel, treating its new primes independently. Removing primes just discards coordinates. No binary value of $T$ is needed.

Fix a squarefree divisor $B$ of the basis product $T$ and put $P=T\mathrm{/}B$. Restrict the representation of $X\in [0,T)$ to basis $B$ to obtain $R=X<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>B$ in $[0,B)$, and extend $R$ back to basis $T$ by step 4.1. For each $p\mid P$, compute $(X-R)B^{-1}<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>p$, where $B<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>p$ and its inverse are fixed short constants from step 1.1. This is the representation of $Q=\lfloor X\mathrm{/}B\rfloor$ modulo $P$; since $0\le Q<P$, it is the canonical one. Extend it from basis $P$ to basis $T$ by step 4.1. If $P=1$, output zero; if $B=1$, return $X$. All componentwise operations are short lookups. This proves constant-depth logspace-uniform division by these fixed squarefree products without assuming general binary division.

Let $X\in [0,M)$ be given in basis $M$ and fix $1\le s<N$. Put $A={\prod }_{i=1}^s{A}_i$ and $P=MA$. Extend $X$ to basis $P$ by step 4.1. Compute each fixed $A_i$ modulo each basis prime and add one componentwise. This represents $A_i+1<P$. Since $2\mid P$ and $A_i$ is odd, step 5.1 computes $H_i=(A_i+1)\mathrm{/}2$ in basis $P$. Using step 2.1, compute $Y=X{\prod }_i{H}_i$ in that basis. There is no wraparound, since $H_i<A_i$ and $X<M$ imply $Y<P$. Divide by $A$ with step 5.1 to obtain $Q=\lfloor Y\mathrm{/}A\rfloor$ in basis $P$.

We have $Y\mathrm{/}A=(X\mathrm{/}{2}^s){\prod }_i(1+1\mathrm{/}{A}_i)$. Since $A_i>M$ and $M>2^{N+4}>s(s+1)$, the binomial coefficients bounded by powers of $s$ give ${\prod }_i(1+1\mathrm{/}{A}_i)<(1+1\mathrm{/}M{)}^s\le {\sum }_{j\ge 0}(s\mathrm{/}M{)}^j=1+\frac{s}{M-s}<1+\frac{s+1}{M}\mathrm{.}$ Consequently $0\le Y\mathrm{/}A-X\mathrm{/}{2}^s<(s+1)\mathrm{/}{2}^s\le 1$. Thus $Q$ is either $\lfloor X\mathrm{/}{2}^s\rfloor$ or that integer plus one. Retain $Q$ unless $Q{2}^s>X$, in which case subtract one. The comparison in basis $P$ is valid without wraparound: $Q{2}^s<X+2^s<M+2^N<2M<P$. Compute the residues of $2^s$ by step 1.1, multiply componentwise, and compare by step 3.1. Subtraction by one is componentwise and occurs only when $Q\ge 1$. The selected vector represents $\lfloor X\mathrm{/}{2}^s\rfloor$, whose residue modulo $2$ is bit $s$ of $X$. Bit zero is already the residue of $X$ modulo $2$. Thus all $N$ bits are recovered by parallel copies of a constant-depth circuit.

Convert the $m$ input words to basis $M$ by step 2.2 and multiply their residue vectors by step 2.1. Their exact product $Z$ satisfies $0\le Z<2^{mw}=2^N<M$, including zero factors, so this is its canonical residue vector. Apply step 3.2 and step 6.1 and step 7.1 in parallel at every index $s<N$. The result is its exact binary product, with precisely $mw$ output bits and leading zeros where required.

Every basis length, prime value, table argument, loop index and word width above is polynomially bounded in $N$. In step 3.1, the approximant width is $O(k^{\mathrm{\prime }}\log U)$ for its polynomial-size basis length $k^{\mathrm{\prime }}$, hence polynomial as well. Each table has a fixed number of short arguments and polynomially many rows. Each conversion, comparison, extension and division uses a fixed finite number of layers of tables, Boolean gates and [F3]; their nesting in step 1.1 and step 2.1 and step 2.2 and step 2.3 and step 3.1 and step 4.1 and step 5.1 and step 3.2 and step 6.1 and step 7.1 and step 8.1 has depth independent of all dimensions and prime counts. Trials over primes, residues, table rows and output bits are parallel copies. Thus the total size is polynomial and depth constant. Label gates by their stage and a fixed number of polynomially bounded coordinates. A logspace machine enumerates the fixed prime lists, computes needed residues by repeated modular multiplication, computes power and discrete-log table bits as in step 1.1 and step 2.1, and decides local wiring using short counters. The composition depth of subcircuit descriptions is fixed, so intermediate descriptions can be recomputed using $O(\log (N+2))$ workspace. The machine never stores $M,P,A_i$ or another long product. The addition circuits from [F3] are also logspace-uniform. This proves both logarithmic-space description generation and the gate-predecessor predicate, completing the Statement.

At the fixed input let $R=R(n)$ and let $A$ count accepting strings among the $2^R$ fair-bit strings, including unused suffixes after early halting; then $p=A\mathrm{/}{2}^R$ by [F1]. The new machine first reads $R+2$ selector bits, rejecting only the all-zero selector. On every nonzero selector it simulates the original machine for at most $R$ steps using $R$ fresh bits, records its outcome, and consumes any unused suffix bits in a no-op state. On the zero selector it consumes all $R$ fresh bits and rejects. By [F3] this is a well-defined clocked procedure. There are exactly $2^{2R+2}$ equiprobable strings and exactly $(2^{R+2}-1)A$ accepting ones, so $p^{\mathrm{\prime }}=(1-2^{-(R+2)})p$.

If $p\le 1\mathrm{/}2$ then $p^{\mathrm{\prime }}<1\mathrm{/}2$. If $p>1\mathrm{/}2$, then $A\ge 2^{R-1}+1$, so $p-1\mathrm{/}2\ge 2^{-R}$; because $p\le 1$, $p^{\mathrm{\prime }}-1\mathrm{/}2=(p-1\mathrm{/}2)-p{2}^{-(R+2)}\ge 2^{-R}-2^{-(R+2)}>0$. Thus strict majority is preserved and an original tie becomes a strict no-instance.

The new acceptance probability cannot equal one half: such equality would require the integer $A$ to equal $2^{2R+1}\mathrm{/}(2^{R+2}-1)$, which is not an integer because its denominator is odd and greater than one. Since no tie remains, swapping accepting and rejecting labels makes the complement machine accept strictly above one half exactly on the original no-instances. The selector and padding add $2R+2$ transitions, so the overhead is $O(R(n))$.

Specify the syntax rather than appealing to an arbitrary effective code. Use canonical binary numeric fields, each encoded as $1^{\mathrm{\mid }w\mathrm{\mid }}0w$, and encode a tuple of $a$ such fields by $1^{a}0$ followed by their encodings. Supply two complete transition tables, one for each fair-bit value. The virtual input tape is read-only, each work tape is initially blank, and each head starts at cell zero with clamped left motion. The finite input alphabet is the two binary input symbols, distinguished from blank. A header lists the tape count $k$, alphabet size $r$, state count $m$, start and two distinct halting states; the two tables list every nonhalting state/scanned-symbol tuple in lexicographic order, each with its next state, written symbols, and local moves or stationary requests. For the read-only tape require its written symbol to equal the scanned symbol. All integers use canonical binary numerals, all blocks carry unary length headers, and the number of blocks is unary-prefixed. Include explicit table delimiters and a profile tag. This is prefix-free, includes each finite machine of the chosen numeric form, and has a total decoder. If the start state is nonhalting, a complete table contains at least one row with $k$ symbol/move fields and contains all nonhalting states and scanned symbols, giving $k\le L$, $r\le L+3$ and $m\le L+3$. An initially halting machine will instead be handled without per-tape initialization by an early return after validation. Each stored integer has at most $L$ bits even without these sharper bounds.

For this erased-index interpreter put $H=n+b+L+2$, $s=\lceil {\log }_{2}H\rceil$ and $B=2^s$, so $B>n$ and $B>b$. Use the explicit unary-length tuple syntax from the sequential candidate, now adding finite head labels, the source index-tape labels, a profile tag, index-output actions and native jump actions to each transition row. A row specifies all source actions, and the complete table explicitly includes every state/scanned-symbol/bit case. For nonhalting start states, at least one such row exists, so the number $h$ of source heads and index tapes, every alphabet width, and each instruction-record width are bounded by a fixed polynomial in $L$. Initially halting machines use that early return. The source's one binary work tape is included as a special case; any allowed finite additional tapes receive tape labels. Parse and validate by capped expected-count arithmetic without expanding an asserted table; this takes $L^{O(1)}$ time. State and scanned-symbol lookup by repeated scans of the saved table costs $L^{O(1)}$ per source transition. The fixed physical interpreter never acquires a new head or an alphabet depending on $e$.

Parse and check the actual blocks without expanding a claimed table. Count the actual rows first; compute expected products and powers by binary arithmetic capped one above that actual count, rejecting excess, invalid ranges, missing rows or extra data. If there are no nonhalting states, the expected row count is zero without computing a power or iterating over tape/head labels. Check each actual row's arity against the binary header by counting its actual fields, never by a loop of header-specified length. This bounds all valid and invalid code processing by a polynomial in $L$: the operands, counters and scans have length $O(L)$, there are $O(L)$ actual blocks, and every product/exponent loop is capped or uses at most $L$ exponent bits. Ordinary repeated scans and school arithmetic suffice, for example in $O(L^6)$ time and $O(L^2)$ space. After validation, if the start state is halting, report that outcome immediately, even for $b=0$, without allocating or initializing per-tape or per-head structures. Otherwise the parameter bounds of steps 1.1 and 1.2 apply to all following phases. Preserve a decoded table of length $O(L^2)$, runtime parameters and fixed-width symbol/state codes of width at most $L+O(1)$. Copy $x$ to a sequential archive and read/copy the clock in $O(n+\log (b+2))$ time. All subsequent routines use fixed physical tape counts and fixed alphabets; variable-size data remain on tapes.

For each source index tape reserve a separate contiguous region of $b+1$ binary cells, with its current length stored in metadata. Reserve these regions by arithmetic base offsets before the dictionary heap; reservation moves no head through the regions and requires no initialization sweep. A source index emits at most one bit per source transition, so its live word always fits. Appending a source bit writes at its region's base plus current length and increments that length. Use/reset sets the length to zero; future emission overwrites old bits, and reading only the current prefix ignores the discarded suffix. Interleaved emission onto different source indexes therefore never interleaves their physical words. Since at most $h$ bits are emitted per source transition, the sum $W$ of lengths of all words consumed at jumps, plus lengths still live at expiry, satisfies $W\le hb$, up to a harmless fixed-format constant. A jump using one word for several source heads in the same transition multiplies this accounting by at most $h$, still a polynomial in $L$. Reading, copying or canonicalizing each consumed word once, or a fixed number of times per affected head, therefore has total length $L^{O(1)}b$. The reserved regions' total extent is $O(h(b+1))$, consistent with later maximum-address bounds. This charged fresh-writing invariant is exactly what fails for the old nonerasing delimited-head model.

Split each numerical source head address $a$ uniquely as $a=PB+r$, where $0\le r<B$. Call $P$ its block prefix and $r$ its short offset. Store the short offset in $s$ bits. Maintain a global prefix dictionary assigning one compact integer block ID to each registered numerical prefix. A dictionary key for $P$ is the prefix-free word $1^{\mathrm{\mid }w\mathrm{\mid }}0w$, where $w$ is the canonical binary numeral of $P$, including $w=0$ at zero. Use a literal binary trie: each node has two child pointers, an optional terminal block ID and its fixed metadata. Reading/inserting a key follows or creates one node per bit. Numerical equality of prefixes is equality of their canonical words, hence exactly equality of terminal nodes. No balancing, probabilistic hashing, numerical unit-cost large integers or unspecified dictionary theorem is required. Include a tape label in this key when more than one virtual work tape is allowed.

For each virtual tape, store its scanned cell as a centre and the cells on either side as two ordered stacks, nearest cell first. At level $i$, put $h_i=2^i$; each side has capacity $2h_i$, occupancy $0,h_i$ or $2h_i$, and complementary occupancies summing to $2h_i$. Initially each side has occupancy $h_i$ at every level; the right stack holds the input suffix on the input tape and blanks elsewhere, and all left stacks are blank. Each record has an immutable origin bit, one exactly for source cell zero; it moves with the symbol record. Genuine records are packed at the near end of each zone, and concatenating zones while ignoring holes gives the stack. Each physical slot has $k$ delimited virtual fields, each of width at most $L+O(1)$, containing a symbol and an immutable origin bit, or a hole. Store the $k$ centre fields and the $k$ three-valued occupancy flags explicitly. A slot therefore has width $O(L^2)$; this uses no alphabet depending on $e$ and no additional physical tape for each virtual tape. A stationary move changes only the centre symbol. At the left origin a requested left move also changes only that symbol. For the input tape suppress writes. These modifications preserve the same stack and origin invariants.

On a source head's jump, read the consumed address word, discard leading zeros and split off its final $s$ bits as $r$, padding on the left with zeros if the word has fewer than $s$ bits. The remaining canonical prefix is $P$, or zero. Form canonical $P-1$ when $P>0$, $P$ and $P+1$ by ordinary binary scans; forming all three costs $O(A+s)$ for address-word length $A$. Register them in the prefix trie. Record their three compact IDs as a private cache for this head, and record that the current block is the middle one. Use a special clamped boundary marker instead of a negative block when $P=0$. Initialize each source head at address zero with this same cache for zero and one. If several source heads jump to the same address, their numerical prefixes receive the same global IDs. The total number of prefix-trie nodes is at most the total length of all registered keys, hence at most $L^{O(1)}(b+1)$: for each jump, all three prefix keys have length $O(A+1)$, and step 2.2 charges their summed lengths. Duplicated registrations only decrease the node count. Tape-label overhead adds at most $L^{O(1)}$ bits per jump.

Implement a move to the right by first writing the old centre $c$ and choosing the least $i$ with a nonempty right zone. All lower right zones are empty and their left partners full. Remove the first $h_i$ records of right zone $i$: the first becomes the new centre, and the remaining $h_i-1={\sum }_{j<i}{h}_j$ fill the lower right zones in order, $h_j$ per zone. Right occupancy at level $i$ decreases by $h_i$. Prepend $c$ to the concatenation of the lower left zones. The resulting $1+2{\sum }_{j<i}{h}_j=2h_i-1$ records split into a first list of length $h_i-1$, distributed in order half-full among the lower left zones, and a remaining list of length $h_i$, prepended to left zone $i$. Its previous occupancy was zero or $h_i$, so no capacity is exceeded. Both stacks keep their order, complementary occupancies at level $i$ are preserved, and every lower zone becomes half-full. For $i=0$ these instructions simply exchange a stack record with the centre and push the old centre on the other stack. A left move interchanges left and right; at the origin it only writes the centre. Untouched higher zones are half-full, so a source zone always exists. Thus every operation preserves the representation and performs exactly the prescribed source move.

Between two jumps of this head, its address changes by at most $b$ in total absolute distance from its most recent jump address, since every local move changes it by at most one and there are at most $b$ source transitions altogether. As $B>b$, every intervening address belongs to one of the three blocks $P-1,P,P+1$ cached at that jump. A local move updates the $s$-bit offset; overflow/underflow switches to the appropriate adjacent cached ID and wraps the offset. Store the current cache position as one of three finite values. Even if the head crosses the same block boundary many times, the existing IDs are reused, with no re-reading or arithmetic on long prefixes. From the lower cached block it cannot cross to an uncached lower block, and from the upper cached block it cannot cross to an uncached upper block: either would require more than $B$ local moves since the jump. Clamp a left move at numerical zero. Thus the pair (current block ID, short offset) is always an exact address representation, with $O(\log H+\log L)$ bits after accounting for the polynomial number of trie nodes.

Make the scan algorithms uniform as follows. To process virtual field $j$, keep a unary field index of length at most $L$; at each slot count through the delimited fields, copy or replace just field $j$, and copy the other fields unchanged. A full slot, its index operations, and returning a scratch head across the bounded parameter records cost at most $O(L^4)$. The same bound covers building one fresh slot by copying the saved width and tape-count templates. Midpoint/end markers specify half-zones, so the scans need no growing arithmetic per record. Copying the selected genuine field records to scratch, distributing the prescribed lists, restoring holes and flags, and returning the physical heads use a fixed number of prefix scans for step 4.1; at level $i$ they traverse $O(2^i)$ slots. Endpoint and optional level-label overhead is also $O(2^i)$, since the sum of the binary level-label lengths through $i$ is $O(2^i)$. Thus the work for a level-$i$ event on one virtual tape is at most $C_1{L}^6{2}^i$, uniformly in $e,i$. This deliberately generous bound includes scans to find the least nonempty source zone, scratch copying, occupancy changes and allocating new levels by doubling the preceding unary capacity marker. Each operation is a scan, a finite-width copy, or an index operation of length at most $O(L)$; no unit-cost random memory operation is being assumed.

The event count is independent of field width. Fix a virtual tape and $i\ge 1$. Its right occupancy below level $i$ starts at $H_i=2^i-1$. Each event at level at least $i$ resets it to $H_i$; a lower-level positive or negative move changes it by minus or plus one, and a stationary or clamped move leaves it fixed. An event at level at least $i$ requires the appropriate lower stack empty, hence occupancy zero or $2H_i$ immediately beforehand. It therefore requires at least $H_i$ preceding lower-level moves and then its triggering transition. Among $b$ simulated transitions there are at most $\lfloor b\mathrm{/}{2}^i\rfloor$ such events, including the first. Level zero has at most $b$ events, and no level with $2^i>b$ is reached. The redistribution in step 4.1 resets all lower zones even when its level is strictly larger than $i$; successive operations on different virtual tapes do not change each other's fields.

Maintain a second literal binary trie for virtual work cells, keyed by the compact block ID and the $s$-bit offset, with explicit length delimiters (and virtual tape label if needed). The key length is $O(\log H+\log L)$. Every terminal stores the virtual symbol, initially zero/blank on first lookup. Each source transition touches at most $h$ virtual cells, so there are at most $h(b+1)$ terminal keys and $L^{O(1)}(b+1)\log H$ nodes in this trie. All keys with the same virtual cell get the same terminal, regardless of which source head or which jump registered that prefix. Source work-tape collisions can therefore be detected by comparing these compact address pairs for all relevant heads, in $L^{O(1)}\log H$ work per transition. Omit precisely the operations declared undefined by the source's collision convention. Read all source scanned symbols and save all source instructions before any virtual write or move.

Initially retain the input archive at position one and initialize only the centres. On first allocating level $i$, fill the first virtual tape's untouched right half from the next $h_i$ archive symbols, then blanks after exhaustion; initialize the other virtual fields with blank and unoccupied halves with holes. Levels are allocated in increasing order, and lower operations do not alter that untouched suffix, so every archive symbol is consumed at most once. A new level uses only the work charged to the event reaching it. Initially right zone $i$ represents source positions $2^i,\dots ,2^{i+1}-1$; hence the archive is exactly at the next untouched interval. Slot creation and symbol coding are charged by step 5.1. Thus no full $n\log n$ distribution pass is hidden in initialization.

Before each virtual transition, test the saved state, then test expiry. If still nonhalting with positive countdown, consume one fresh fair bit to choose the corresponding decoded table. Deterministically scan its rows and compare the source state/scanned-symbol tuple with the saved state and centres, copying the unique instructions into scratch. At most $O(L)$ rows and $O(L^2)$ saved fields are involved; repeated full scans and resets take $O(L^6)$ per transition. Save all instructions before applying any virtual write/move, process the $k$ buffer operations in order, then update the state and decrement the binary countdown. Test the new halting state before the next expiry test, so a halt on transition $b$ is reported. A whole countdown scan costs $O(\log (b+2))$ per virtual transition. At $b=0$ the nonhalting initial configuration expires immediately.

Treat read-only input separately. Since $n<B$, an input-head address is in range only if its block prefix is zero and its short offset is an input position. The global trie has the distinguished ID for zero, so this is a comparison of compact IDs followed by comparison of $s$-bit integers. On an in-range address issue a native input query with the original short address, or its fixed encoding-offset translation if the physical interpreter input is a paired encoding of $(e,x,b)$. This translation has $O(\log H)$ bits. On an out-of-range address return the source's prescribed blank. The same compact head representation implements local input moves and jumps. The original input is never expanded into the work-cell trie.

Store the two tries, the reserved source index-word regions, finite-program records, per-head caches, short counters and scratch on allocated regions of the interpreter's single binary classical work tape. Encode record delimiters and symbols by constant-length binary blocks. Long key/input-word arrays have total length $L^{O(1)}(b+1)$; trie nodes and other records have length $L^{O(1)}\log H$. The cell trie has $L^{O(1)}(b+1)\log H$ nodes by step 5.3. Consequently every physical location used is below $L^{O(1)}(b+1){\log }^{O(1)}H$, and every pointer has $O(\log H+\log L)$ bits. No source's enormous numerical address is used as a physical memory location. Reserve the polynomially sized source-program/scratch region and the $O(h(b+1))$ source-index regions by arithmetic offsets, then use a global high-water counter to append-allocate the dictionary heap and saved long keys. This reserves address intervals without writing their unused cells.

Buffer correctness from step 4.1 and the saved-instructions ordering imply by induction that after each virtual transition the interpreter stores the exact virtual configuration prescribed by the consumed bits. Although the physical probabilistic machine receives a bit at every physical transition, ignore all of them except at the designated virtual-choice operation. Conditional on every past consumed bit and the corresponding completed deterministic simulation, the next designated bit is still unbiased and independent: its location depends only on previous bits, and disjoint future coordinates of a finite independent-bit string have the prescribed fair conditional law. Equivalently, for each fixed virtual choice prefix of length $j$, induction on its successive designated choice operations gives probability $2^{-j}$; ignored physical bits have total conditional probability one. Terminal virtual prefixes are disjoint. Summing their masses proves exact agreement of acceptance/rejection/timeout probabilities, including branch-dependent halt times.

Summing step 5.1 using step 5.2, first for each tape and then over $k\le L$, bounds total buffer and lazy-allocation work by $C_2{L}^7(b+{\sum }_{i=1}^{\lfloor {\log }_{2}b\rfloor }{2}^i\lfloor b\mathrm{/}{2}^i\rfloor )\le C_2{L}^{7}b(1+\lfloor {\log }_{2}b\rfloor )$ when $b\ge 1$. Add polynomial code processing, the $O(n)$ input archive scan, transition lookup, and the binary-clock work. The physical heads move locally by at most one cell per transition, as required by the sequential profile. Enlarging the absolute exponent to $d=8$ and the constant covers all contributions, the binary-clock input length, and $b=0$. This proves the general displayed bound.

Choose one pointer width $q=K(s+\lceil {\log }_{2}L\rceil +1)$ at initialization, for an absolute constant $K$ exceeding all fixed exponents in step 6.4. Node-count and record-length bounds there imply that the allocated region is smaller than $2^q$; indeed its logarithm is $O(\log L+\log (b+1)+\log (s+1))=O(\log L+s)$. Thus all pointers, lengths and allocation counters can be padded to $q$ bits, and every trie node has fixed-width updatable pointer fields; no shifting of a long suffix or variable-record reallocation is needed. A fixed set of physical work heads accesses a record by emitting its short physical pointer on its own one-way erased index tape, taking $O(q)$ transitions, making the native jump, and reading or updating that record by local scans. Pointers, offsets and record metadata have polynomial-in-$L$ times logarithmic length, so each trie-node operation and each elementary bit-array read/copy takes $L^{O(1)}{\log }^{O(1)}H$ physical transitions. Each concrete record operation is a bounded number of short-address accesses, scans, and ordinary binary arithmetic. This constructs a fixed-head interpreter in the same erased-index profile; its address emission is charged, and no head count depending on $e$ has been assumed.

If $\mathrm{\mid }e\mathrm{\mid }\le c{\log }_2(n+2)$ and $T(n)\le (n+2{)}^q$ for fixed $c,q$, then $L^8=O({\log }^8(n+2))$ and $\log (T(n)+2)=O(\log (n+2))$. Construct unary $1^n$ by a sequential input scan, run the fixed constructor in [F4], and use its binary output as $b$. Since $T(n)\ge n$, initialization, construction and simulation together use $O(T(n){\log }^9(n+2))$ time. The interpreter's simulated transitions remain sequential throughout. This proves the stated specialization without asserting a corresponding bound for arbitrary superpolynomial clocks or for VMW jumps.

Sum the work. Prefix registration uses $L^{O(1)}(b+1)$ key-bit operations by step 2.2 and step 3.2, plus at most $O(s)$ splitting/offset work per jump. Every source transition performs $L^{O(1)}$ program/head/short-counter operations and at most $L^{O(1)}$ work-cell-trie lookups, each traversing $O(\log H+\log L)$ nodes. Native input queries and the binary countdown take polynomially many short-record operations per source transition. Multiply by step 7.3's cost per operation, add the $O(n)$ initial input scan and polynomial code parser, and enlarge one absolute exponent $d$ to obtain the proposed time bound. Step 6.4 independently bounds maximum physical work-head address by that time bound. This normalization is for time-only use: it does not preserve the original source's smaller space bound.

At each simulated configuration, test the source halting state before expiry. If nonhalting and the countdown is positive, take one designated fresh fair bit, select the source table, perform the deterministic operations above, and decrement. The dictionaries preserve exact source-cell equality and values, the prefix/offset invariant preserves exact head addresses, and the index arrays preserve exactly the source's newly written addresses and erasure. Induction on source transitions therefore reproduces the full source configuration up to expiry, including simultaneous actions and source collision semantics. A halt on transition $b$ is reported; a still-nonhalting configuration at expiry rejects. Ignore physical fair bits at all operations except the designated one-per-source-transition choice. Conditional on each consumed prefix, the next designated bit is an independent fair bit, so each source choice prefix of length $j$ has mass $2^{-j}$. Summing over disjoint terminal choice prefixes proves exact probability preservation.

For $L=O(\log (n+2))$ and fixed polynomially bounded $b=T(n)\ge n$, both $L$ and $\log H$ are polylogarithmic in $n+2$. The displayed general bound is consequently $O(T(n)\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}(n+2))$. Scanning $x$ to construct unary $1^n$ costs $O(n)$. Its fixed deterministic time-constructible constructor runs in $O(T(n))$ sequential time. Execute that fixed local-move machine using the already proved external-clock erased-index interpreter with successive budgets $1,2,4,\dots$, restarting from its initial configuration until it halts and yields the binary clock. This uses no advance knowledge of $T(n)$: the last budget is $O(T(n))$, the sum of the budgets is $O(T(n))$, and the repeated input scans cost $O(n\log (T(n)+2))$. Since $T(n)$ is polynomially bounded and at least $n$, the whole constructor simulation is $O(T(n)\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}(n+2))$, absorbed in the specialization. A deterministic constructor ignores the interpreter's designated fair bits. The sequential interpreter of phases 1–4 gives the specialization for the sequential profile. Neither argument identifies the erased-index profile with the old delimited-head profile.

Store each simulated binary work tape unchanged on a physical binary tape, initially zero, and maintain its fixed finite head addresses with $O(\log (n+2))$-bit counters. Since all work accesses are below $M$, every valid work-head/index endpoint value is bounded by $M$. Accumulate a freshly emitted source index bit by shift-and-append, saturating work indices at $M$ and ordinary input-head indices at $N+T+1$. A work overflow cannot be used on the promised run; appending bits cannot undo it. An overflowing input jump remains outside the input for every remaining local step, so a FAR marker returns blank until the next jump. Index lengths and emitted contents are unread except on use; these numeric summaries and resets therefore implement exactly their observable effects. Each counter operation, short physical index emission, head read/write and input-position comparison costs polylogarithmic time and logarithmic workspace. Physical input-head read at position $i<N$ calls the generator of $y_i(x)$, using charged short erased indices for its source-input reads. Outside that range it returns blank.

For each simulated work tape keep a second zero-initialized binary tape containing the heap representation of a complete binary OR tree with $M$ leaves. Leaf $M+a$ stores work bit $a$ for $0\le a<M$, and internal node $j$ stores the OR of nodes $2j,2j+1$. Initially every value is zero, matching the source; no initialization sweep is needed. When work bit $a$ changes, update its leaf and ascend through $\lfloor j\mathrm{/}2\rfloor$ to the root, recomputing each OR from its two children. At most $1+{\log }_{2}M$ nodes are visited; every address is below $2M$ and takes $O(\log (n+2))$ bits to emit. Thus an update costs polylogarithmic time with only a fixed number of logarithmic counters. The invariant follows inductively because only ancestors of the changed leaf can change. Arbitrarily many zero cells require no explicit allocation or stored pointers.

The OR of work interval $[l,r)$ is found in at most $2{\log }_{2}M+2$ tree-node reads. Initialize the accumulated OR to zero and put $L=M+l$, $R=M+r$. While $L<R$, if $L$ is odd include node $L$ and increment $L$; then if $R$ is odd decrement $R$ and include that node; finally replace both by their integer halves. Return the accumulated OR when $L=R$, in particular zero without a node read when $l=r$. At each iteration the included fringe nodes are disjoint, and the remaining uncovered interval is the union of the complete sibling pairs between the updated endpoints; halving replaces precisely those pairs by their parents. Induction proves that the included nodes partition exactly the original leaf interval. Each level includes at most two nodes, and there are at most $1+{\log }_{2}M$ levels. Their stored OR is therefore exactly the requested range OR. The procedure uses logarithmic counters and polylogarithmic time.

Implement a native source query with $u\le v$ as follows. Put $k=\lceil {\log }_2(N+1)\rceil$, and inspect the last $\min (k,v-u)$ address bits immediately before $v$, using short physical addresses. Let $p=\max (u,v-k)$. Query the tree OR of $[u,p)$. If it is one, the binary input address is at least $2^k>N$, so the native query leaves its answer unchanged. Otherwise the entire numerical address is the inspected low word, padded with leading zeros to $k$ bits. For $1\le i\le N$, generate $y_{i-1}(x)$ and XOR it into work bit $v$, then update that tape's OR tree as in step 2.1. For an invalid index leave the answer unchanged. The empty address gives zero and hence no change, and reversed endpoints are omitted as specified by [F1]. Only $O(\log (n+2))$ work-bit reads, a range-OR query, one generator call and one update are needed. Every accessed physical work/tree address is $O(M)$, and only logarithmic scratch is used. The source address word can be reused indefinitely; the maintained tree avoids rescanning its long high part.

Ordinary source local operations change only a fixed finite number of bits, so apply step 2.1 to each changed bit after taking the source's simultaneous reads and respecting its collision rule. Source input queries are exact by step 1.1 and step 4.1, and all head/index transitions are exact by step 1.1. Induction on the source clock therefore gives the identical source configurations and branch outcomes, with the harmless FAR summary of permanently blank input positions. The simulator takes exactly one designated independent fair bit per source transition and ignores all its other physical fair bits; each source choice prefix has its original mass $2^{-j}$. All auxiliary work is deterministic, so outcomes and acceptance probabilities are identical. At most a polylogarithmic amount of work is done per transition, plus the initial $O(n)$ input-length setup. Source work and OR trees have extent $O(M)$ on fixed finitely many tapes, and every generator/counter needs $O(\log (n+2))$ workspace. These are exactly the claimed time and space bounds.

Fix the machine. Its input-head positions, finite state and logarithmic workspace have at most $n^c$ configurations, for a fixed integer $c$. A halting deterministic computation cannot repeat a configuration, so increase $c$ to bound its running time by $n^c$. Make both halting states absorbing. A configuration has $O(\log n)$ bits, including the conventional bounded input positions, charged input-address registers if used, finite state and work symbols. Small input lengths can be decided separately.

Put $b=\lfloor \sqrt{n}\rfloor$ for sufficiently large $n$. To assert that configuration $u$ reaches $v$ in exactly $\mathrm{\ell }$ steps, existentially specify $b-1$ intermediate configurations. Divide $\mathrm{\ell }$ into $b$ consecutive intervals whose lengths differ by at most one. Universally select one interval and assert the corresponding endpoint reachability for that shorter length. This equivalence follows by taking the actual intermediate configurations in the forward direction and concatenating all verified segments in the reverse direction. Iterate for a fixed $r>2c$ levels; continue until the selected interval has bounded constant length. Indeed the recurrence ${\mathrm{\ell }}_{j+1}\le {\mathrm{\ell }}_j\mathrm{/}b+1$ gives ${\mathrm{\ell }}_r\le n^c\mathrm{/}{b}^r+2$, bounded by three for a sufficiently large fixed $r>2c$. At each level the existential list uses $O(\sqrt{n}\log n)$ bits, and the universal index uses $O(\log n)$ bits. Zero-length intervals demand equal endpoints.