Can local computation preserve its past at constant cost?

Research questions and checked implications, 4 October 2026.

The question is whether mutation adds essential power when every command can inspect and change only a bounded local neighborhood. Imagine two registers pointing to the same mutable cell. Changing the cell through one register affects what the other register will read. An immutable simulator must reproduce that shared behavior by allocating new records, while preserving the old state and still answering before the next command arrives.

The broader goal is to characterize which future behaviors admit such finite-rule representations with bounded local access and allocation. A strong possible answer is that every locally changing finite-data computation has a constant-overhead immutable representation. If true, retaining every past state would follow from locality in this model. If false, a separating behavior would reveal an additional structural obstruction.

This is a candidate statement, not an established theorem. The comparison below establishes a classical logarithmic simulation, explains why a known separation does not apply to a finite command alphabet, and shows that full persistence follows automatically from a uniform worst-case immutable simulation. It does not settle the candidate or establish that this exact formulation is a new open problem.

The statements worth reaching

The last two statements are competing outcomes of one investigation. A particular decision diagram becoming large does not establish the third statement. The grid comparison supplies a useful control: a different representation can still support efficient future queries.

First test: a stronger compiler fails

The binary permutation argument rules out constant-overhead immutable compilation that also preserves structural routing independent of current payload values. It adapts a classical counting method and charges the entire finite-alphabet input. Candidate C remains unresolved because its target may use value-dependent routing. If C holds, that freedom is sometimes essential.

The same investigation shows that excluding an explicit source pointer-equality instruction does not weaken C up to constants: a temporary scratch mark implements the test by mutation and is cleared before the command ends. The target must realize that behavior by some other means. This concerns whole-state simulation, not free comparison of arbitrary externally supplied handles.

Access to replay is a separate obstruction

The review of replay access and compilation separates whole-program transformation from a library around an unchanged opaque component. A published higher-order separation rules out uniformly cheap reusable checkpoints in an affine-handler language, under its original function interface. It does not refute C. Correct continuation-passing compilation changes the interface, and its operational simulation theorem is not already our bounded-local cost theorem.

The next bridge must account for both suspended control and store versions: reusing a continuation that shares a mutable bit can produce different outputs from forking the entire original state. The priority is a precise compilation/access contract, not another permutation exponent.

Candidate C: eliminate mutation without losing the clock

Fix a deterministic machine $M$ with finite control, finite node labels, a fixed number of root registers and a fixed bound on outgoing pointer fields. Its initial graph is fixed and finite. A command comes from a fixed finite alphabet. Each command causes at most $c_M$ primitive operations and returns one symbol from a fixed finite output alphabet, possibly a designated silent symbol.

A primitive reads a label or field at a register, moves or copies a register, changes a label or field, or allocates a constant-size node. Pointer values come only from registers, fields actually read, or fresh nodes. Cycles and arbitrarily many incoming references are allowed. There is no address arithmetic, ordering of addresses, unbounded scalar, hidden oracle or explicit pointer-identity test. Mutation can nevertheless make sharing observable through later label reads.

The target uses finite control and finite-tag, bounded-arity records whose fields are fixed when allocated. Physical pointers point to older records, so its heap is acyclic. Its only data access is a bounded local pointer operation; it has no pointer-identity test, late field filling, mutable memo table or uncharged suspended computation. Its entire active state consists of a fixed number of registers and finite control. Initialization is fixed and finite.

Candidate C. For every such $M$, there are one target machine $I_M$ and constants $K_M$ and $A_M$ such that, for every finite command sequence, each command is processed in at most $K_M$ target primitives and $A_M$ fresh records, with the same output before the next command is accepted.

The constants may depend on $M$, not on input length, graph size or history. Correctness concerns all future command/output behavior. The target need not reproduce $M$’s physical graph. Thus a different representation is allowed, while a delayed answer is not. Existence of $I_M$ is the immediate claim; an effective transformation from $M$ to $I_M$ would be an additional result.

This is much stronger than computability equivalence. It is also distinct from a linear aggregate bound that permits one arbitrarily expensive command.

A checked implication: versions come with a uniform immutable simulation

Suppose the simulator in C exists. At each command boundary, save its register tuple and finite control in a constant-size immutable snapshot. Resuming a supplied snapshot restores that tuple in constant work. Its reachable heap has not changed. Records allocated by other branches cannot affect its execution because the simulator has no ambient mutable state or address-dependent observations.

Induction over any finite tree of commands therefore gives the same outputs on every branch. If $H$ commands are actually executed, even on repeatedly selected old states, total work and fresh storage are $O(H)$. Every individual command retains the uniform bound. Conversely, restricting a branching implementation to one branch gives the single-trace guarantee.

Consequently, under this exact contract,

$$\text{uniform constant-cost immutable realization} \quad\Longleftrightarrow\quad \text{uniform constant-cost fully persistent realization}.$$

This elementary snapshot argument is a written implication, independently reviewed, not a novelty claim or formal verification. It matters strategically: full persistence need not be a separate conjecture once the required immutable worst-case simulator exists.

The client supplies a previously returned snapshot handle. Finding a version by an integer name is additional charged work. Combining the contents of two versions is also a separate operation. An amortized guarantee does not suffice: repeatedly forking just before a costly command can repeat its cost without replaying the earlier cheap commands used to pay for it.

A baseline that already works

There is a general immutable simulation with $O(\log(d+2))$ worst-case work and fresh records for a command issued from a version at command depth $d$. Across $H$ executed commands its total work and allocation are $O(H\log(H+2))$. This is classical balanced-store simulation and path copying, with the following explicit accounting for our contract.

Assign each simulated node a binary identifier, unique within its version. Store the simulated heap in a persistent binary trie; a leaf contains a finite label and a fixed tuple of identifier-string roots. Keep the simulated root registers, control, next identifier and trie height in the version handle. A source cycle becomes a cycle among decoded identifiers, not a physical cycle in the target heap.

There are at most $C_M+c_Md$ allocated source nodes along one branch. Identifier length and trie height are therefore $O(\log(d+2))$. Lookups follow key bits. Updates copy the affected path. Temporary traversal stacks, key construction and counter increments all cost $O(\log(d+2))$ local work and allocation. These are bit-list operations, not unit-cost integer arithmetic. When capacity doubles, prepend a trie root with the old trie on its zero branch; a unary height list supports leading-zero padding of older keys within the same bound.

The invariant is that the version’s trie gives exactly that version’s simulated fields. Allocation uses an unused identifier; copied paths preserve older roots. Induction over the version tree proves correctness. Sibling branches may reuse numerical identifiers because each lookup uses its own version’s trie. Mixing node handles from different versions is outside this contract. The same construction can simulate explicit source identity tests by comparing identifier strings, although candidate C does not need that extension.

All historical and temporary allocations count. With $R=O(H\log(H+2))$ target records, a conventional serialized pointer encoding uses $O(R\log(R+2))$ bits. No variable-size prepared graph is free: constructing it contributes commands and cost. For a finite command history, the alphabet is fixed and the history length is its input size up to a constant factor. Selecting earlier handles is an additional client interface, not an uncharged integer-address oracle.

The target gap is thus concrete: can the logarithmic overhead always be eliminated under C, or does some finite-data behavior force an unbounded overhead? We are not assuming that the classical upper bound is tight here.

What the literature permits us to say

Local rules already have broad classical characterizations. Arrighi and Dowek’s Causal graph dynamics, Definitions 9, 14 and 15 and Theorem 1, characterize causal dynamics by local rules. Their rules act across a bounded-degree graph synchronously; one global tick can involve many vertices. This does not give constant total sequential work or immutable history. Their Theorem 3 uses finite state sets for the continuity characterization. We should not rename this result as a new FPRD theorem.

Bounded observations must also control selected locations. Gurevich and Yavorskaya’s A more abstract bounded exploration postulate, Definition 2.4, Postulate 4, Example 2.5 and Theorem 3.1, make accessibility of update locations explicit. Their model includes equality patterns and abstract primitive functions. Our concrete pointer costs and absence of identity observations require a separate translation.

A known separation has a crucial alphabet hypothesis. Pippenger’s Pure versus Impure Lisp, Theorems 1.1-1.2, gives an online symbolic $O(n)$ versus $\Omega(n\log n)$ separation and a general logarithmic simulation. Section 3 gives the balanced-store baseline used above. Section 4, especially report p.8, explains why its lower-bound argument fails for a finite input alphabet. Therefore it does not refute C. Encoding distinct symbols by finite strings changes the charged input and output work; the separation must be reproved after that change.

Persistence results have resource and mutation contracts. Driscoll, Sarnak, Sleator and Tarjan’s Making Data Structures Persistent, Sections 2-3, give bounded-indegree persistence transformations with amortized update bounds; printed p.116 discusses prior path copying. Section 6, printed p.122, states a write-once modification and a linear pure-LISP consequence under bounded indegree. Those results demand a careful comparison with immutable-at-allocation records, worst-case deadlines and arbitrary incoming sharing. Historical open questions in that paper are not evidence of present-day open status.

Functional syntax alone does not specify the implementation. Bird, Jones and de Moor’s A Lazy Pure Language versus Impure Lisp gives a linear lazy solution to Pippenger’s workload. Its abstract distinguishes assignments used by the evaluator from source-language assignments. Any proposed use here must account for evaluation, sharing and retained versions in the target’s actual immutable model.

A substantial known positive case

Complete checkpoints for locally navigated trees imports Demaine–Langerman–Price’s functional trie theorem: fixed-degree trees with a fixed number of cursors support local edits and cross-version subtree copying in constant time and allocation in the published model. The exact finite-rule consequence is stated conditional on a costed catenable-deque primitive. This is classical, not evidence that C has been proved. Several cursors at one tree occurrence are supported; shared mutable aliases across distinct structural paths are a different contract. Deep trees and limited cross-version composition must be positive controls for any proposed characterization.

A conditional positive case with genuine shared mutation

Finite shared cores extend the tree control: arbitrarily many mutable references may target a fixed finite set of permanently marked nodes. Under the explicit local catenable-deque premise, the written construction preserves all aliases and old versions at constant cost per specified command. Independent components with disjoint declared core names admit a constant-cost join. This is a classical-method reduction, with novelty unestablished. Unbounded incoming degree alone is therefore not the desired obstruction. Unbounded target identities and scope composition remain consequential tests.

Closure under nested ownership

Scoped checkpoint composition gives a written conditional closure theorem: fixed shared-core regions can nest without a global bound on identities, provided child ownership is unique, live references do not escape, and scope movement is explicitly charged one level at a time. A zipper of costed local headers supports arbitrary focused snapshots and repeated root-focused value grafting with reused local names. This uses classical methods; it is not a general ownership theorem. A live exported pointer to an old child header fails after the owner is updated. The next significant issue is interface consistency across escaping references or independently active scopes, not another container variant.

A sharp obstruction at a live-reference component boundary

Stable references impose a lookup cost rules out constant-cost immutable implementation of an unbounded Boolean store when original external handles must remain valid in every state. In the finite-label, bounded-arity, identity-blind model, worst-case Read costs at least logarithmic time even with unrestricted preparation, update work and storage. A persistent binary trie matches the read bound. The proof allows data-dependent routing and quantifies over all representations in the specified interface; it uses classical finite-neighborhood counting, with novelty unestablished.

This closes the naive universal component-interface strengthening of C. It does not close C itself: routing a location through a finite command stream is charged and the compiler can transform the whole caller state. The same investigation shows why counting bounded-length observable futures alone cannot separate closed finite-alphabet machines. Any finite future table can be represented as a prepared immutable command tree; the unresolved cost is producing and maintaining useful representations online.

Consequences and decisive tests

If C holds, the finite-command behaviors of the specified mutable local machines and immutable local machines coincide with constant worst-case overhead. The snapshot implication supplies full persistence and linear total historical allocation. That would turn many separate persistence constructions into instances of one principle.

A refutation would separate local computability from locally maintainable immutable futures in a finite-data model. To have that force, it must quantify over all permitted immutable representations, rather than one store layout, canonical form or source-code translation.

Neither outcome alone solves independent-fragment composition. A mutable client must still perform its actual combination and query work. A simulator cannot turn an expensive compatibility test into one primitive. Cross-version joins also require an explicit meaning for identities, shared state and conflicting updates; the snapshot theorem does not supply it.

The next decisive test is a primary-proof comparison of the strongest whole-program mutation-elimination results against C’s exact finite-alphabet, immutable-at-allocation, worst-case contract. Follow the finite-alphabet qualification in Pippenger and the evaluator mutation in lazy alternatives through their actual constructions. Determine whether an existing uniform construction settles C or supplies a substantial sufficient mechanism, or whether a resource-preserving counterexample survives charging the caller’s routing. Current open status and novelty remain unestablished.

The stable-external-handle contract is now closed at matching logarithmic read cost. Do not refine its constants or import its lower bound into C by deleting index-acquisition work. Likewise, the positive tree/core/ownership controls are sufficient examples, not a necessary structural classification. A general proposal must explain online construction cost, not merely enough static capacity for future answers.

The intrinsic characterization remains the larger destination. The existing finite-quotient theorem with uniform context application is a restricted positive case, not that complete destination. Primitive-only behavior, effective routing, successor readiness and meaningful composition remain essential parts of the broader question.