Remembering a computation is not the same as being able to resume it

Literature assessment and a conditional consequence, 4 October 2026.

Imagine a component that examines a sequence of yes/no answers before returning a result. We want to explore every possible answer sequence. Two runs often share a long beginning. Saving that beginning would help, but only if the caller can ask the component to continue from it with a different answer.

Our broader goal is to understand future behavior maintained by finite rules with bounded local access and allocation. A powerful proposed statement is that any local computation can acquire cheap, reusable checkpoints. The literature makes us separate transforming the entire computation from adding a library around an unchanged component. The latter has a rigorous obstruction in an established higher-order model. The former remains the subject of candidate C.

A strong established comparison

Hillerström, Lindley and Longley study counting the satisfying inputs of a predicate supplied as a function. Their canonical predicates inspect each of $n$ input coordinates exactly once along every path, with arbitrary Boolean leaves. In their abstract-machine model, Theorem 5 forces every correct generic counter using affine handlers to spend $\Omega(n2^n)$ time on canonical predicates containing a true leaf. Affine means a captured resumption can be used at most once. For the same pure input class, Theorem 2 gives a reusable-resumption counter costing

$$\sum_{v\in T_P} w_P(v)+O(2^n),$$

where $w_P(v)$ charges the predicate’s own work between queries. For uniformly bounded such costs, this is $O(2^n)$.

The lower proof changes one leaf: correctness forces every leaf to be reached. Single-use resumptions keep each application on one path, and its $n$ tests cannot be shared across successful applications. The positive proof explores both answers from a retained resumption. See the 2024 paper, Definitions 7–9, Theorems 2, 3 and 5, §§4.3 and 10; its positive proof continues in the 2020 version, Appendix C.

This is imported mathematics, not a new FPRD separation.

A consequence for a proposed checkpoint library

Here is an exact way to test the ambitious library claim. Work within the affine language and cost model of that theorem. For each $n$, suppose a library accepts any canonical predicate through its unchanged function interface, without inspecting or transforming its code. Suppose it offers this service:

• Initialization reaches the first query or answer.
• A query checkpoint can be retained and advanced with either Boolean answer, repeatedly, without invalidating the retained checkpoint.
• Advancing reaches the next query or terminal Boolean answer.
• The resulting tree is exactly the predicate’s query tree, including its leaf answers.

The library may represent checkpoints however it likes, provided its implementation is a program in the affine language. Calling a representation a “snapshot” does not grant an extra primitive. The premise requires correctness on every canonical predicate, not just a chosen easy family.

Let $A_n$ bound its entire initialization and preparation. Let $d_n$ bound the cost of each subsequent advance, including all internal execution, reconstruction and deferred work, uniformly over those predicates and checkpoints. Bounds are runtime costs in the cited model, not uncharged oracle operations.

A depth-first client could use the service to count all true leaves in

$$O\bigl(A_n+(d_n+1)2^n\bigr)$$

steps: retain a checkpoint, explore its two children, and add their counts. Its client stack has one frame per active level. The retained checkpoint is reusable data by the hypothesized service contract. The composite library and client would itself be an affine-language generic counter.

The imported lower bound therefore implies

$$\boxed{A_n+(d_n+1)2^n=\Omega(n2^n).}$$

In particular, preparation $A_n=o(n2^n)$ cannot coexist with $d_n=o(n)$. Constant-time advancement with inexpensive preparation is impossible under this contract. This is a direct conditional consequence of the published theorem, not a separate originality claim. It excludes every library implementation in that language satisfying the stated interface, including clever encodings, rather than just a stack-copying implementation.

The qualification is decisive. It does not exclude a compiler that can transform the predicate itself, a runtime exposing reusable continuations, or a different language outside the theorem’s model. It also does not establish a lower bound for arbitrary first-order pointer machines.

Why an explicit representation changes the answer

Consider exactly the same canonical query tree, now supplied as an inspectable immutable tree rather than hidden behind function application. Each internal record contains its two child pointers and a coordinate identifier; each leaf holds a Boolean. On the promise that every path tests all coordinates once, counting needs only a traversal of the leaves. It need not perform a fresh root-to-leaf evaluation for every input vector.

A stack-based traversal sums the counts of child subtrees. At height $h$ above the leaves, a count has at most $h+1$ bits. There are $2^{n-h}$ subtrees of that height. Ordinary bit-list addition, including newly allocated result lists and temporary stacks, therefore costs at most

$$O\left(\sum_{h=0}^{n}2^{n-h}(h+1)\right)=O(2^n).$$

The output has at most $n+1$ bits. This is a written elementary construction using fixed finite labels and bounded local operations, with $O(2^n)$ additional historical allocation. No unit-cost unbounded integer is needed. Coordinate identifiers need not be inspected during counting because the input is promised canonical; checking that promise is a different task.

This is deliberately an expensive explicit input, not a compact-formula result. If the tree is serialized in preorder with a fixed-width binary coordinate identifier at each internal node, its actual description length is

$$N=\Theta\bigl(2^n\log(n+2)\bigr).$$

Reading and constructing its pointer representation costs $O(N)$, so the full construction and count cost $O(N)$. We claim no exponential-in-$n$ lower bound for polynomial-size inputs. In the opaque-function comparison the predicate is supplied as a callable value; neither its syntax nor a prepared leaf-count annotation is available to the client. Supplying either changes the problem’s access contract.

The control matters: the mathematical function being counted has not changed. The ability to inspect or resume its representation has.

Compilation is a different quantifier

Hillerström, Lindley and Atkey give a continuation-passing translation to a plain lambda calculus in Effect Handlers via Generalised Continuations, §§5.2–5.4 and Theorem 7. The translation passes explicit continuation structure through translated computations. Its simulation theorem and backward-simulation corollary establish operational correctness. They do not by themselves establish our constant-cost finite-register pointer compilation theorem.

There is no conflict with the checkpoint obstruction. Translating the component and its caller changes how they communicate. A library receiving the original opaque function cannot simply declare that the function now accepts an explicit continuation parameter. Thus the following statements must be kept distinct:

There are also real implementation obligations between abstract steps and our machine model. Environment lookup, closure construction, handler search, arithmetic and continuation copying must all be charged. A linked persistent stack permits sharing its root; copying an entire stack instead can erase the speedup. The bit-counting calculation above discharges arithmetic for the explicit-tree control only. It does not translate the full higher-order language into a bounded-local machine.

Reusable control still need not preserve the store

A small counterexample prevents a second overreach. Suppose a suspended computation will toggle a Boolean cell and return its new value. The cell initially contains zero. If two resumptions share that mutable cell, the two results are one and then zero. If each branch resumes a complete snapshot of the original state, both results are one.

Thus a reusable continuation that retains control and references into a shared store is not automatically a fully persistent state. The distinction is observable with one bit and two resumes; it requires no address arithmetic or identity test. Our candidate C concerns the entire represented state, whereas the generic-counting separation uses pure input predicates. Importing the latter does not discharge store versioning for arbitrary mutable components.

How this changes our research priorities

The strongest useful lesson is that storage and access to suspended control are separate resources. We should not search for a theorem saying merely that “remembered work can be replayed.” A theorem must say who can obtain a checkpoint, what the checkpoint includes, which branches may reuse it, and what preparation exposes it.

The next decisive investigation is a resource-preserving bridge: take a precisely defined finite-data component with explicit code and account for the cost of exposing resumable states, including its private mutable store. A successful translation must give one uniform construction and charge code loading, environment access, capture, resumption and every historical allocation. If it fails, the failure must identify an operation or interface obstruction, not merely a slow chosen representation.

This takes priority over sharpening the permutation lower bound. The subsequent tests are whether independently prepared components can agree on the required checkpoint interface without hidden cross-component access; whether replay must include shared-store versions as well as control; and whether the positive and negative cases admit one non-circular structural condition. These are tests of a possible foundational statement, not claims that it has already been found.

The present outcome is a literature-backed obstruction and an exact separation of research questions. No new representation-independent theorem for our first-order machine class, proof-assistant verification or current-open-status claim is made.