Time normalization of classical basis queries

First construct and justify the only balancing procedure used below. An insertion-only AVL tree is a binary search tree with each node storing its key, two child pointers, a parent pointer, height, subtree size and optional OR aggregate. Set the height of an empty subtree to zero. Maintain that the two child heights differ by at most one. A tree of height $h$ has at least $N_h$ nodes, where $N_0=0$, $N_1=1$ and $N_h\ge 1+N_{h-1}+N_{h-2}$. For $h\ge 2$ this implies $N_h+1\ge 2(N_{h-2}+1)$, since the minimum sizes are nondecreasing. Induction therefore gives $N_h+1\ge 2^{\lfloor h\mathrm{/}2\rfloor }$, so $h\le 2{\log }_2(N_h+1)+1$. Consequently the invariant implies logarithmic root-to-node paths, without any distributional assumption on keys.

Search by the ordinary ordered comparisons. An absent key is inserted as a leaf at the null child where search ends. Retrace its ancestor path, recomputing height, subtree size, and OR aggregate from each node's two children and its own value. Until the first unbalanced ancestor, each subtree height increases by at most one; these metadata updates are required whether or not a rotation occurs. If no ancestor is unbalanced, the height invariant already holds. Otherwise let $z$ be the lowest unbalanced ancestor. Suppose its left height has become two greater than its right height; the opposite case is the left/right reflection. Let $y$ be its left child. The child $y$ cannot have equal child heights: if its new child heights were $t,t$, one child would be unchanged at $t$, so its old maximum child height would already have been $t$ and its own height would not have increased. Thus the new child heights of $y$ differ by one. If $y$ is left-heavy, write the heights of its left subtree, its right subtree and $z$'s right subtree as $t+1,t,t$. Rotate right at $z$, making $y$ the root of this local subtree. Its right child is now $z$, whose two child heights are $t,t$, hence whose height is $t+1$; $y$'s two child heights are both $t+1$, hence its height is $t+2$. Recompute the fields of the rotated nodes bottom-up, then continue the metadata updates above the repaired subtree. All local balances are valid. The old pre-insertion subtree at $z$ also had height $t+2$, so this restores that old height.

In the remaining left-heavy case, $y$ is right-heavy. Let $w$ be $y$'s right child. Write the heights of $y$'s left subtree and $z$'s right subtree as $t,t$. The two child subtrees of $w$ have heights each at most $t$, at least $t-1$ when nonempty as required by AVL balance, and maximum $t$. Rotate left at $y$, then right at $z$, making $w$ the local root. Its left child $y$ now has child heights $t$ and at most $t$ differing by at most one, hence height $t+1$; its right child $z$ has the analogous heights and also height $t+1$. The root $w$ has height $t+2$, again the old pre-insertion height at $z$. This also covers $t=0$, where the relevant empty children have height zero. The right-heavy cases are exact reflections. Rotations preserve the in-order key sequence: the single rotation changes $((A,y,B),z,C)$ to $(A,y,(B,z,C))$, and the double rotation changes $((A,y,(B,w,C)),z,D)$ to $((A,y,B),w,(C,z,D))$. All nodes retain their stable identities, while a constant number of child/parent pointers change. After this first repair the subtree's old height is restored, so higher ancestors cannot acquire a new imbalance. Recompute height, size and OR first on the lower rotated nodes, then their new root, and then along the remaining ancestor path. Thus search and insertion use $O(\log (N+2))$ node operations, and maintain all stated fields. This proves the needed AVL result locally; no deletions will be used.

For each virtual binary work tape keep an outer insertion-only AVL tree whose keys are canonical numerical block prefixes $P$ in the representation $a=PB+r$, $0\le r<B$. Each outer node has a permanent compact block ID equal to its stable allocation ID. Store a canonical binary prefix word and its length at that node. To compare a freshly supplied prefix of length $A^{\mathrm{\prime }}$ with a stored prefix, first compare their lengths, which are short integers. If unequal this decides numerical order; if equal compare their $A^{\mathrm{\prime }}$ bits lexicographically. Each comparison costs $O(A^{\mathrm{\prime }}+\log H+\log L)$ elementary short-address/bit operations, including access to the stored key. Search/insertion makes $O(\log (N+2))$ such comparisons by step 1.1 and step 2.1 and step 3.1. Only head-jump or query-endpoint registration requires such a fresh-key search. As in [F1], on every registration also register $P-1$ if nonnegative and $P+1$, whose canonical words can be formed by ordinary scans in $O(A^{\mathrm{\prime }}+1)$ work. The sum of all these key lengths is $L^{O(1)}(b+1)$ by fresh-index charging in [F1]; duplicate keys are not stored twice. This bounds all long-prefix reading and key comparison costs by $L^{O(1)}(b+1)\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}H$. Initial prefix zero and its neighbor one add only fixed keys per virtual tape.

Every outer node owns an inner insertion-only AVL tree of all offsets so far accessed in that block. Its keys are $s$-bit offsets; its node stores the current binary cell value. Keep nodes even when their value becomes zero, so deletion is unnecessary. The inner subtree OR is the OR of its nodes' cell values. The outer node's own OR is its inner root's OR, or zero for an empty inner tree; its subtree OR combines its own OR and the two outer child subtree ORs. A new cell is initially zero, and then receives any prescribed write. Each source local operation accesses only $L^{O(1)}$ cells. A query will access at most $k+1$ individual cells in addition to its range-OR operation below. Hence the number of inner nodes is at most $L^{O(1)}(b+1)(k+1)$. Searching/inserting an offset costs $O(\log (N+2))$ comparisons of $s$-bit keys. A bit-value change recomputes OR along its inner ancestor path and then along its owning outer node's ancestor path; rotations maintain the same aggregates by step 3.1. Thus one short-offset access/write costs $L^{O(1)}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}H$ physical work. Unregistered prefixes and absent offsets represent zero cells.

The parent pointers and subtree sizes allow numerical comparisons of already registered block IDs without rereading their possibly long keys. Compute the in-order rank of a known node $v$ as its left-subtree size plus one, then ascend to the root, adding one plus the ancestor's left-subtree size whenever the current node is that ancestor's right child. Every node visited contributes exactly the keys preceding $v$ that lie in the corresponding ancestor piece, so the result is the exact one-based numerical rank. This uses $O(\log (N+2))$ short-record operations by step 1.1. Stable node IDs and current parent/size fields remain valid after rotations. No insertion occurs while the ranks of one operation are being used. Two compact cell addresses are compared by these outer ranks and then their short offsets. Local head moves use the same three cached adjacent-prefix IDs as [F1]: between source jumps a head travels at most $b<B$ cells, so cannot leave those three blocks. In particular repeated crossings of a block boundary cost only short-offset arithmetic and cached-ID selection. They never incur another long-prefix comparison.

Prove the range-OR procedure explicitly. In an AVL tree whose nodes have in-order ranks, sizes and OR aggregates, the OR of a contiguous rank interval is obtainable in $O(\log (N+2))$ node visits. At a subtree, its root rank and child rank intervals are computed from a carried starting rank and the left size. If a subtree's whole rank interval is inside the query interval, use its stored aggregate; if disjoint, skip it; otherwise recurse on the intersecting children and include the root's own value if its rank is in the interval. At each depth only subtrees containing one of the two query boundaries can require recursion: at most two partially intersected subtrees, together with at most a constant number of their fully included/disjoint children. Thus total visits are $O(\text{height}+1)$. Inner offset trees use ordinary $s$-bit key comparisons to locate offset bounds, with the same procedure or the corresponding two boundary paths. For a source address interval $[a,c)$, if both endpoints have the same block ID, query that inner offset interval. If their block IDs differ, OR the suffix of the left inner tree, the prefix of the right inner tree, and the outer subtree range strictly between their numerical ranks. Registered endpoint prefixes exist by registration, even if their inner trees are empty. All untouched cells contribute zero. This computes exactly the OR of every source work bit in $[a,c)$, including arbitrarily large gaps of unvisited zero cells, in $L^{O(1)}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}H$ work.

Realize the data structures in the index-only target by the fixed physical protocol in [F1]. Source index words occupy separate $b+1$-cell reserved regions; arithmetic reservation does not scan them. Store the long prefix words in append-allocated arrays. Allocate each outer/inner node as a fixed-width binary record with short child/parent pointers, height/size, current bit or inner-root pointer, and OR fields. The outer-node count and total long-key length are $L^{O(1)}(b+1)$; the inner-node count is $L^{O(1)}(b+1)\log H$. All record lengths are $L^{O(1)}\log H$, so the largest physical address is $L^{O(1)}(b+1){\log }^{O(1)}H$. Select a padded pointer width $q=K(s+\lceil {\log }_{2}L\rceil +1)$ for a sufficiently large absolute $K$; the preceding bound is smaller than $2^q$. Every pointer, height, size and low-offset arithmetic operand fits in polynomially many $q$-bit fields. A constant number of fixed physical heads, reserved scratch regions, emitted short erased input/work indices and ordinary local scans implements each elementary node or array-bit operation in $L^{O(1)}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}H$ transitions, as in [F1]. No extra physical head per source head, arbitrary alphabet extension, unit-cost large-integer operation, or long uncharged address is used.

On a source basis query, consume and register the two fresh endpoint index words, with their neighboring prefixes, as in step 4.1. Save the answer bit at address $v$. Starting from endpoint $v$, take at most $k$ virtual predecessor steps, stopping at $u$. Each predecessor uses only short-offset arithmetic and the cached three-prefix neighborhood of $v$, because $k\le b<B$ for $n\ge 1$; when $n=0$, $k=0$ and no predecessor step is needed. Record the encountered bits, in reverse order, to obtain the last $\min (k,v-u)$ address bits. Comparisons with $u$ use compact ranks/offsets from step 5.2, not long key strings. Let $p$ be the position reached, namely $\max (u,v-k)$. Query range-OR on $[u,p)$ using step 6.1. If that OR is one, some address bit more significant than the last $k$ bits is nonzero, so the query address is at least $2^k>n$ and the answer must stay unchanged. If it is zero, the entire numerical input address is the recorded low word, padded with leading zeros to $k$ bits. Compare that short integer $i$ with $1$ and $n$. Outside $1\le i\le n$, leave the answer unchanged; inside this range, emit the physical input address for bit $i$ (subtract one, then add any fixed paired-input encoding offset) on the index-only target's ordinary input index tape, make the native classical input read, and XOR the retrieved input bit into the saved answer cell. In the empty-address case $u=v$, the low word is zero and $x_0=0$ as specified. This exactly implements $Q_x$ on all basis work configurations, while never invoking a block query in the target. The source address register can be reused indefinitely; each operation uses aggregates and short accesses rather than rescanning that register.

The charged long-prefix operations total $L^{O(1)}(b+1)\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}H$ by step 4.1. Each source transition additionally uses $L^{O(1)}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}H$ for finite-table lookup, short head updates, collisions, ordinary cell reads/writes, and at most one fixed finite number of basis queries. A basis query contributes at most $k=O(\log (b+2))$ short cell accesses, a constant number of rank/range-OR operations, and a short emitted input index, all bounded by the same type of polylogarithmic factor. Multiply by the short-record physical cost from step 6.2, add the $O(n)$ input-length scan and polynomial code initialization, and enlarge the absolute exponent $d$ to obtain the theorem's bound. The same allocation bound proves the asserted time-scale maximum address. This is solely a time normalization; the dictionary need not respect a smaller original source space bound.

Use [F1]'s external-clock driver: test halting before expiry, consume one designated fresh fair bit for the next source table, save the complete source instructions, and apply their operations with the source's simultaneous-action and collision conventions. Ordinary source operations are exact by [F1] and the compact numerical address/value invariants; a source block query is exact by step 7.1. Induction reproduces the entire source basis configuration after each simulated transition. All added dictionary, balancing, rank, OR and input-read work is deterministic. Ignoring physical fair bits except the designated source choices therefore preserves every consumed source prefix's probability $2^{-j}$; summing disjoint terminal prefixes preserves acceptance, rejection and timeout probabilities exactly. A halt on transition $b$ is reported, and nonhalting expiry rejects.

For descriptions of length $O(\log (n+2))$ and fixed polynomially bounded clocks $b=T(n)\ge n$, both $L$ and $\log H$ are polylogarithmic in $n+2$, so step 8.1 gives $O(T(n)\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}(n+2))$ time. A fixed deterministic clock constructor can first be simulated by the already proved index-only external-clock interpreter with doubling budgets, as in the combined clocked candidate, with total time $O(T(n)\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}(n+2))$. The resulting index-only target is included in the basis-query profile. Thus the time-hierarchy diagonal can use this normalized interpreter in the basis-query profile, and Cook-style trace encodings can use its bounded-address index-only computation. This does not identify sublinear-time basis-query and index-only classes, and transports no original source-space bound.