Charged construction, filtering and retention of separator-component state records
ProvedStableMSR.Recovery.Compiler.StateRecord.accepted_state_record_programOne deterministic program of instructions constructs and tests a candidate graph-component state, then appends its exact separator-component key precisely when accepted. The ordinary input consists of a separator bitmap , a complete directed arc list for an undirected graph , a seed , a width bound , a table base and row count , and writable work regions. No component bitmap, boundary bitmap, connectivity certificate, or new table record is supplied.
Let be the vertices reachable from by walks avoiding , and let be its external boundary. Acceptance is exactly
An accepted candidate appends one record consisting of the separator bits, the computed component bits, and a zero initialization payload. The new row count is . Every old record is preserved, including when keys repeat. A rejected candidate leaves the count at and preserves both all old records and the next free record. Initial table cells and writable masks may contain arbitrary data.
For vertices and listed arcs, including repetitions, the actual charged interpreter halts within
steps, including candidate construction, the validity branches, record addressing, both key-half copies, payload write, metadata restoration and one final halt. The separator, edge array, input metadata, all real data, oracle/tape counts and cells outside the specified work regions and new record are preserved under explicit memory-separation hypotheses. The code is fixed before all input dimensions and data. Width zero, inside seeds, oversized separators and empty arc lists are included; a seed requires .
This connects actual component-state construction to actual state-pair table writes. The payload is an initialization value. Complete table coverage across the seed and separator sweeps, recurrence/DP evaluation, graph construction from the recovery input, geometry and the full clustering recovery program remain separate obligations.
import Definitions.Def_StableMSR_ComponentGraphMemory open scoped Classical open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.ComponentMemory
theorem StableMSR.Recovery.Compiler.StateRecord.accepted_state_record_program :
∃ P : MinSumFPT.Program, DeterministicProgram P ∧ P.length = 221 ∧
∀ (n w q : ℕ) (d : Point n → Point n → ℝ) (G : SimpleGraph (Fin n))
(S : Finset (Fin n)) (es : List (Fin n × Fin n)) (seed : Fin n) (s : Store),
s.ptrs 5 = (es.length:ℤ) → s.ptrs 6 = (n:ℤ) → s.ptrs 17 = (seed.val:ℤ) →
s.ptrs 43 = (w:ℤ) → s.ptrs 62 = (q:ℤ) →
Bitmap s.imem (s.ptrs 3) S → EdgeEncoding s.imem (s.ptrs 2) es →
Separate (n := n) (s.ptrs 3) (s.ptrs 4) →
Separate (n := n) (s.ptrs 3) (s.ptrs 50) → Separate (n := n) (s.ptrs 3) (s.ptrs 51) →
Separate (n := n) (s.ptrs 4) (s.ptrs 50) → Separate (n := n) (s.ptrs 50) (s.ptrs 51) →
EdgesSeparate (s.ptrs 2) (s.ptrs 4) es → EdgesSeparate (s.ptrs 2) (s.ptrs 50) es →
EdgesSeparate (s.ptrs 2) (s.ptrs 51) es →
(∀ r : Fin (q+1), ∀ j : Fin (n+n+1),
let x := s.ptrs 61+(r.val:ℤ)*((n:ℤ)+(n:ℤ)+1)+(j.val:ℤ)
(∀ v : Fin n, address (s.ptrs 3) v ≠ x ∧ address (s.ptrs 4) v ≠ x ∧
address (s.ptrs 50) v ≠ x ∧ address (s.ptrs 51) v ≠ x) ∧
(∀ a (ha : a < es.length), s.ptrs 2+2*(a:ℤ) ≠ x ∧ s.ptrs 2+2*(a:ℤ)+1 ≠ x)) →
(∀ e ∈ es, G.Adj e.1 e.2) → (∀ u v, G.Adj u v → (u,v) ∈ es) →
∀ (ω : ℕ → ℝ) (work : ℕ),
∃ t ≤ n*(17*es.length+57)+17*es.length+4*q+113,
let C := Finset.univ.filter (fun v : Fin n => ∃ p : G.Walk seed v, ∀ z ∈ p.support, z ∉ S)
let B := Finset.univ.filter (fun v : Fin n => v ∉ C ∧ ∃ u ∈ C, G.Adj u v)
let accepted := seed ∉ S ∧ S.card ≤ w ∧ S = B
let base := s.ptrs 61+(q:ℤ)*((n:ℤ)+(n:ℤ)+1)
let result := (MinSumFPT.step P d ω)^[t] (s.state 0 work)
result.halted = true ∧ result.work = work+t ∧
result.cfg.ptrs 18 = (if accepted then 1 else 0) ∧
result.cfg.ptrs 62 = ((q+(if accepted then 1 else 0):ℕ):ℤ) ∧
(accepted →
(∀ v : Fin n, result.imem (base+(v.val:ℤ)) = if v ∈ S then 1 else 0) ∧
(∀ v : Fin n, result.imem (base+(n:ℤ)+(v.val:ℤ)) = if v ∈ C then 1 else 0) ∧
result.imem (base+(n:ℤ)+(n:ℤ)) = 0) ∧
(¬accepted → ∀ a : Fin (q+1), ∀ j : Fin (n+n+1),
result.imem (s.ptrs 61+(a.val:ℤ)*((n:ℤ)+(n:ℤ)+1)+(j.val:ℤ)) =
s.imem (s.ptrs 61+(a.val:ℤ)*((n:ℤ)+(n:ℤ)+1)+(j.val:ℤ))) ∧
(∀ a : Fin q, ∀ j : Fin (n+n+1),
result.imem (s.ptrs 61+(a.val:ℤ)*((n:ℤ)+(n:ℤ)+1)+(j.val:ℤ)) =
s.imem (s.ptrs 61+(a.val:ℤ)*((n:ℤ)+(n:ℤ)+1)+(j.val:ℤ))) ∧
Bitmap result.imem (s.ptrs 3) S ∧ EdgeEncoding result.imem (s.ptrs 2) es ∧
(∀ x : ℤ, (∀ v : Fin n, x ≠ address (s.ptrs 4) v) →
(∀ v : Fin n, x ≠ address (s.ptrs 50) v) → (∀ v : Fin n, x ≠ address (s.ptrs 51) v) →
(x < base ∨ base+(n:ℤ)+(n:ℤ)+1 ≤ x) → result.imem x = s.imem x) ∧
result.cfg.regs = s.regs ∧ result.cfg.mem = s.mem ∧
result.queries = s.queries ∧ result.tapePos = s.tapePos ∧
(∀ j : ℕ, j ∈ ([2,3,4,5,6,17,43,50,51,61]:List ℕ) → result.cfg.ptrs j = s.ptrs j) := by sorry