Revision kernels and finite-horizon risk

A revision can pass today's test and destroy the ability to pass tomorrow's. A query can reduce uncertainty while leaving an incompatible possibility alive. To follow these differences precisely, we need a cost recurrence, a preservation kernel and a risk calculation that retains the same hidden context throughout each audit.

This chapter supplies the complete constructions in Appendix A of the published paper. It develops the calculations behind preserving revision and fallible internal inquiry.

A.1: charge the internal query tree

For deterministic serial access, let $S\subseteq Z_p$ be the compatible retained records, $Q$ the unread positions, and $c_p(p')$ the cost of installing and rearming amendment $p'$. A read with its elementary branch costs one unit. The exact worst-case cost of an endorsed amendment into continuation set $X$ is

$$\begin{aligned} D_X(p,S,Q)=\min\Bigg\{& \min_{p'\in\bigcap_{z\in S}[N(p,z)\cap X]}c_p(p'),\\ &\min_{i\in Q}\left[1+\max_{u:S_{i=u}\ne\varnothing} D_X(p,S_{i=u},Q\setminus\{i\})\right]\Bigg\}. \end{aligned}$$(A.1)

An empty minimum is $+\infty$. The first choice installs an amendment valid in every compatible context. Otherwise the first query chooses some unread $i$ and every possible response must be handled. Induction on $|Q|$ proves both the lower bound and attainment.

The unrestricted recurrence assumes that the selected tree can be stored and dispatched. Code, memory or instruction restrictions may exclude it. Then the optimization must range over admitted trees; the unrestricted value is only a lower bound.

For the charter compiler, substitute its unique output $F_{\chi_{\rm old}}(z)$ and charge only record reads. A leaf costs zero exactly when $F$ is constant on $S$; otherwise querying follows (A.1). The publication's exhaustive evaluation over eight initial charters and 32 records yields worst-case depth five for initial AND or OR and four for a projection. Its accompanying verifier computes $F$ by both candidate scan and independent successive filtering, checks all 256 charter-record cases and 1,024 subsequent ordinary executions.

A.2: universal closure with writable validators

When $R(p)$ contains the successors generated by the actual installed revision semantics, define

$$K_0=G,\qquad K_{j+1}=\{p\in K_j:R(p)\subseteq K_j\}.$$(A.2)

The limit consists exactly of configurations whose every finite admitted revision path remains in $G$. Membership implies preservation by induction. If a configuration is first removed at stage $j+1$, it has a successor removed earlier. Following decreasing removal ranks produces a finite path outside $G$. This proves maximality and bounds the shortest removal witness by $|\mathcal P|$, the number of configuration types.

An overapproximate transition relation gives a sound, potentially conservative kernel. Exact classification requires exact composable semantics.

A mutable validator can preserve a fixed property

Attach four validator modes to each of the eight charter programs:

There are 24 locally good types but only 16 universally preserving types: the charter programs with A or B. The installed rule can change A to B when the retained symmetry commitment is active and return B to A. Stored validators need not be immutable. Their outgoing semantics remain part of the proof.

Testing only whether the next program currently passes its local test admits L and misses the later loss. Allowing every syntactically valid charter within a mode overapproximates the actual assessor's smaller successor family. The same 16-type classification is exact for the actual selector: A and B stay among themselves, L actually installs C, and C fails. The conclusion does not assume that every catalogue edge occurs.

A.3: preserve the risk vector before taking its maximum

A query $u$ produces response $y$ under $K_u(y\mid z,h)$. Let $\Pi_B(p)$ be a nonempty finite admitted family of costed observable policy trees, each completing installation. For a continuation set $X$, retain the context-indexed failure vector

$$v_\pi(z)=\Pr_z\{p'\notin N(p,z)\cap X\}.$$(A.3)

A deterministic installation leaf contributes its zero-one loss. A stochastic installation contributes the expectation under its actual kernel. At a query node,

$$v_\pi(z)=\sum_y K_u(y\mid z,h)v_{\pi_y}(z),\qquad r_B(p,X)=\min_{\pi\in\Pi_B(p)}\max_{z\in Z_p}v_\pi(z).$$(A.4)

The context stays fixed through an audit. Maximizing over $z$ separately at each child would allow an adversary to change the retained commitment after the read. For one binary symmetric read followed by installation of the observed value, the true vector is $(\nu,\nu)$; branchwise maximization falsely gives risk one. Endorsement failure, capacity loss and their union can each be propagated.

The policy family fixes the optimization class. If all mixtures of finitely many deterministic trees are available with a charged random source, optimize over the convex hull of their vectors. Randomization can reduce the largest component. With an unread binary commitment and zero queries, the two constant decisions have risks $(0,1)$ and $(1,0)$; their admitted equal mixture gives $(1/2,1/2)$. The positive-read frontier in Theorem 5.2 already covers randomization and has deterministic attaining policies.

Exact finite-horizon failure

The successor $p'$ must contain every accessible variable and history summary affecting future query laws, contexts and resources. Within an audit, its hidden context is fixed. After the terminal history, a new admissible context may be selected from $Z_{p'}$ before fresh query noise begins. This recursion assumes no persistent hidden parameter that constrains those choices or changes later kernels. First-audit and continuation policies must have an admitted, charged composition.

Set $J_H(p)=1$ for $p\notin G$ at every horizon, and $J_0(p)=0$ for $p\in G$. For $p\in G$ and $H\ge1$, a terminal amendment receives the context-indexed loss

$$\ell_z^{(H)}(p')=\begin{cases} 1,&p'\notin N(p,z)\cap G,\\ J_{H-1}(p'),&p'\in N(p,z)\cap G. \end{cases}$$(A.5)

Propagate this vector with (A.4), then minimize its largest initial component. The result is the exact minimum worst-case probability of any endorsement or capacity failure during $H$ audits, including an initially failed capacity.

Proof. Decompose any policy at its first installation. Its immediate failure and best possible continuation give the lower bound. Attaching attaining continuation policies to an attaining first audit gives sufficiency. Induction over $H$ completes the argument. Persistent hidden parameters linking audits require the actual-history uncertainty or likelihood state; this fresh-context recursion does not reset their information legitimately. ∎

The descending iteration

$$X_0=G,\qquad X_{j+1}=\{p\in X_j:r_B(p,X_j)\le\epsilon\}$$

finds the largest set with a uniform one-step risk certificate. It need not optimize every finite-horizon cumulative-risk objective.

If the conditional failure probability after each successful history is at most $\epsilon_i$, multiplication of conditional success probabilities gives

$$\Pr\{\text{some failure by }L\} \le1-\prod_{i=1}^L(1-\epsilon_i) \le\sum_{i=1}^L\epsilon_i.$$(A.6)

No independence of failures is needed. The conditional guarantees and their resource charges are needed. That distinction connects the recurrence back to practical agency: a future capacity is supported by an executable succession of checks, with its remaining risk and resources carried forward.