Uniform clocked simulation of encoded probabilistic machines

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.