Stable references impose a lookup cost

The broader goal is to understand when future computational behavior can be maintained by finite rules with bounded local access and allocation. Here is a strong version of that ambition: could an immutable implementation preserve an ordinary mutable component’s live-reference interface, including references retained by an outside client, with constant work per operation?

For the exact identity-blind model below, the answer is no. Even a collection of independently writable bits forces logarithmic worst-case read time. The conclusion applies to every representation in this model, permits routing based on data, and survives unlimited preparation. A persistent binary trie matches the read bound. This is a statement about an interface, not a refutation of the whole-program candidate C.

The useful distinction is between keeping a few cursors current inside a representation and promising that arbitrarily many unchanged external references will continue to locate their current values. The latter promise requires resolving identity against the selected state.

The strong claim and its precise failure

A client obtains handles $h_1,\ldots,h_n$ for distinct Boolean locations, initially zero. It can retain and copy these handles. A handle denotes the same logical location in every descendant version; it is not a snapshot of that location’s old value. Operations include

$$\operatorname{Set}(v,h_i,b)=v',\qquad \operatorname{Read}(v,h_i)=b_i(v).$$

Set changes precisely that location in the selected version; old versions remain readable. In particular, for every $x\in\{0,1\}^n$, some reachable version $v_x$ must satisfy

$$\operatorname{Read}(v_x,h_i)=x_i\quad(1\leq i\leq n).$$

The handles in this equation are the same previously issued handles for all $x$. How the client locates one in its own collection is outside the component call and is not asserted to be free in a whole program. At call entry it supplies one ready handle and one ready version. The component must perform any conversion, validation needed on valid inputs, or lookup before returning its bit. There is no free handle refresh or replacement prepass.

Fix one deterministic implementation with a finite program and finite record labels. Records have at most $D\geq2$ ordered pointer fields. All fields are fixed at allocation; there are no links from an old record to a later one. A version is a tuple of at most $r$ pointers and one of $F$ finite control/metadata states; $r,F,D$ are constants of the implementation. Each external handle is also a fixed-size tuple of pointers and finite metadata. Handles may point into arbitrarily large prepared structures.

Permitted primitives inspect a finite tag, follow one pointer field, copy a register, perform fixed finite-data tests, or allocate a bounded record from available pointers. Missing pointers can be tested. The machine has fixed registers and finite control. It cannot compare non-null physical pointers, inspect their numerical addresses, use address arithmetic, mutate old records, call an oracle, or invoke arbitrary stored code in one step. Query allocation is allowed and charged. Data-dependent branching and routing are allowed. There is no mutable shared cache or additional ambient state encoding the chosen version. A bounded batch of primitives is normalized into a constant number of these steps.

Stable-handle theorem. For every correct implementation in this model, let $q(n)$ be its worst-case Read work over the reachable versions $v_x$ and all the original handles. Then

$$q(n)=\Omega(\log(n+2)).$$

The constant depends on the implementation. Preparation, Set work, total stored size and the number of old versions may be arbitrarily large and finite. Making them larger does not remove this read lower bound. In fact, the counting argument does not require querying old versions: an immutable implementation of only the current state, with the same unchanged external handles, is already subject to it. Consequently no constant-overhead immutable compiler can preserve this live-reference component interface for all sizes.

The mutable comparison is deliberately narrower: an ephemeral bit-cell implementation reads or writes a supplied cell pointer in constant time without pointer equality. It does not provide old versions. The theorem concerns the stronger promise to eliminate mutation while preserving those external references and adding version-relative reads.

Proof: only a bounded part of a version can matter

For a pointer $p$, form its depth-$q$ labelled unfolding: put its tag at the root, then recursively unfold each ordered field through depth $q$. Null has a distinguished tag and padded null descendants. Repeated occurrences of the same physical node are unfolded separately. This deliberately forgets physical sharing.

The observation argument is the following. If two version tuples have the same depth-$q$ unfoldings and finite metadata, then a query lasting at most $q$ primitives returns the same result on both when supplied the same fixed external handle. Each old pointer reached in that execution originates at a version root, a handle root or fixed initialization. Reaching it requires following an explicit sequence of fields. All such observations lie within the respective depth-$q$ unfoldings. Equal observed tags give equal branch decisions, including data-dependent choices of subsequent paths.

Freshly allocated records do not invalidate the argument. Couple the two executions step by step. Their new records have equal tags and corresponding fields; an old field is represented by its origin and port path, and a new field by the corresponding fresh record. Allocation and copying can preserve aliases, but cannot test whether two such descriptions happen to identify the same old node. Since old records cannot change, there is also no write/read experiment that reveals that coincidence. Induction on the remaining primitive budget therefore preserves every observation and the final output. A query may combine pointers from the handle and version in a new record; that is covered by the same induction.

Let $L\geq2$ bound the tag alphabet including null and all finite record data. The $r$ version-root unfoldings contain at most

$$W_q=r\sum_{j=0}^{q}D^j =r\frac{D^{q+1}-1}{D-1}$$

label positions. Thus there are at most $F L^{W_q}$ observable version types at that depth. Neither the addresses nor the number of inaccessible records enter this count.

Two different Boolean vectors cannot have versions of the same type: choose a coordinate at which they differ and give both versions the same original handle for that coordinate. The observation argument would force equal outputs. Therefore

$$2^n\leq F L^{W_q},\qquad n\leq\log_2F+W_q\log_2L=O(D^q),$$

which proves the bound. It is a worst-case bound over states and queries, not a claim that every read is slow.

An equivalent finite deterministic communication check makes the missing channels explicit. Fix the issued handles and preparation. Alice receives $x$, constructs its version, and sends only its finite metadata and depth-$q$ unfolded tags. Bob receives a coordinate, has the fixed handle structures, and simulates Read from those descriptions. No pointer names or cross-sharing tests are needed because the model cannot observe them. Correctness for every coordinate means Alice’s message distinguishes all $2^n$ vectors, so it needs at least $n$ bits. Its stated length is $O(D^q)$. Address arithmetic, pointer equality, a mutable ambient table, refreshed handles, or version-dependent caller advice would break this particular simulation and are explicitly excluded.

A concrete control shows why physical equality cannot be silently added. Give each location a distinct but identically labelled leaf handle. A root that points to one of those leaves encodes a selected location, and a pointer-equality query recognizes it immediately. All root unfoldings are identical, yet equality against the supplied handle distinguishes them. This invalidates our description protocol in that stronger model; it does not establish constant-time support for all Boolean vectors there. Likewise, mutating the cells behind the original handles invalidates their fixed-view premise.

This is elementary finite-observation counting, closely related to classical pointer-access arguments. It is a written proof, not a claim of a new lower-bound method or a formally verified theorem.

Matching construction and full costs

A binary trie gives a uniform upper bound without any real-time deque assumption. Put the $n$ bits at distinct leaves of a complete binary tree of height $\ell=\lceil\log_2(n+1)\rceil$, ignoring unused leaves. An issued handle points to an immutable list of the $\ell$ bits of its leaf address. It is one ready pointer, not one unbounded integer.

Read walks the address list and the version’s trie together, then returns the leaf bit. It takes $O(\ell)$ local steps and needs no query allocation. Set walks the same route while building a temporary stack of sibling pointers and direction tags, creates the replacement leaf, and unwinds the stack to copy the path. It uses $O(\ell)$ work and fresh records, including the stack. Retaining or restoring a supplied version root is constant work. Every old handle still names the same leaf position in every version.

For an explicit setup encoding consisting of a unary capacity, delimiters, and $n$ initial bits, its length is $N=\Theta(n)$. A conservative preparation algorithm constructs the address lists and tree in $P=O(n\log(n+2))$ work and all-history records. All generation, traversal stacks and identifier bits are included. After $U$ Sets, $R$ Reads and $C$ snapshots/resumes,

$$T=O\bigl(N\log(N+2)+(U+R)\log(n+2)+C\bigr),$$ $$S=O\bigl(N\log(N+2)+U\log(n+2)+C\bigr)$$

bounded-arity records suffice across the entire history. A conventional pointer serialization costs $O(S\log(S+2))$ bits. Version and cell-handle selection by a numerical name has its own input length and routing cost; these formulas start after acquisition of the supplied capabilities. The upper bound matches the theorem’s worst-case read time, not an additional lower bound on updates or storage.

Here the number of independently exposed state bits is $b=n$, if one wants a boundary parameter, and the lower bound is $\Omega(\log b)=\Omega(\log N)$ for that explicit setup. This is not a SAT-fragment encoding or an exponential bound. The proof ranges over possible histories with n Set calls in a fixed coordinate order, each supplying one fresh bit; it does not load a literal table of all Boolean vectors. If those supplied capabilities are instead serialized as numerical names, their actual encoding length and routing work must be added to the complete history input size. The symbol N above denotes the explicit setup size, not that enlarged full transcript. The proof even permits arbitrary preparation and storage: its obstruction is the cold query’s observation interface.

Why this settles an interface but not the larger candidate

The nested-ownership construction failed when a stale child header was treated as a live export. The present theorem is stronger than that counterexample: changing the representation cannot recover constant-time reads for an unbounded set of unchanged exported identities under this precise model. A version authority is necessary to interpret a live handle, and a constant-size version authority is not by itself enough to make arbitrary such interpretation constant-time.

The positive controls survive. A fixed shared core has only a fixed number of independently named targets. A fixed number of maintained cursors can have their representations updated together. Scoped access pays for navigation and return. None promises constant-time cold resolution of arbitrarily many unchanged external handles against every Boolean state.

Candidate C, however, accepts commands from a fixed finite alphabet and allows the compiler to transform the whole state. It does not preserve an unbounded external capability interface. A binary index supplied as command symbols has length $\Theta(\log n)$; the trie can consume it one edge per symbol and return the bit at the deadline. Alternatively a caller reaches a location by charged navigation, during which an implementation can maintain a current cursor. Our theorem cannot erase that work and then reinsert the resulting handle for free.

There is a useful general limitation of the observation argument. Suppose a closed machine has $a$ command symbols and $z$ possible output symbols. Its complete behavior through $m$ further commands has at most

$$z^{\sum_{j=1}^{m}a^j}$$

possible output-labelled command trees. A prepared immutable tree with one outgoing field per command can itself expose any one such finite future one command at a time, at constant work per command. Thus the bare number of short distinguishable futures does not separate these closed finite-alphabet machines: the target can have enough branching capacity. Preparing and maintaining the right tree for an unbounded computation is a different, substantial obligation. No efficient or uniform online construction of those full future trees has been proved here.

This rules out an attractive but insufficient route to the broader characterization: static local observation capacity alone is not an obstruction to C. A consequential next test must account for producing and updating a usable representation throughout a charged history, or identify an observation contract that the whole-program compiler really must preserve.

Classical comparison and remaining scope

Cloteaux and Ranjan’s Lower Bounds for Accessing Information on Pure Pointer Machines (2009), §§2–4, compares information content with bounded-radius access. Their PPM permits pointer equality and mutation; “pure” there means no data fields or arithmetic, not immutable storage. Theorem 3.1 is an incompressibility bound with an index-set-size hypothesis; Theorem 4.1 treats antisymmetry and must preserve shared-neighborhood identity. These theorems are not imported as our bound. Our proof uses fixed old handles and identity-blind unfoldings to count only version-varying information. The methodological comparison is classical; novelty of this exact interface consequence is unestablished.

Demaine, Langerman and Price’s Confluently Persistent Tries for Efficient Version Control, introduction pp.3–4 and §2, makes access discipline central: its positive structure maintains a constant number of fingers and charges navigation. Its functional model forbids changes to old cells. That supplies the relevant positive comparator, not a contradiction to the stable-handle theorem. Their separately discussed RAM/cell-probe persistence bounds use different primitives and are not transferred here.

No machine-recognition, scaffold-to-PEG, unrestricted SAT or P-versus-NP consequence follows. The candidate portfolio retains C as hypothetical. The sharper conclusion is that any broad successful compiler must be allowed to change this component boundary, rather than preserve arbitrary external live references at constant cost.