Canonical-input generation of all bounded-subset table keys with charged execution
ProvedStableMSR.Recovery.Compiler.CatalogCompose.canonical_subset_table_programFor every fixed width , there is a deterministic program of instructions which starts with only the canonical scalar inputs . Let . The program constructs a table of records, each consisting of an -cell subset key and one initialization payload. Every subset of cardinality at most occurs as an exact characteristic key in this retained table, with payload zero; duplicate keys are allowed.
The table begins at integer address . At termination its base and row count are returned in the designated registers, both scalar input cells are preserved, all real registers and memory are unchanged, and no oracle query or random-tape read has occurred. The program halts within
charged instructions, including the final halt. The code is chosen before and the metric input; the statement includes and .
This composes the bounded-word catalog generator and the full catalog-to-table sweep from the canonical input, removing the intermediate-catalog and supplied-layout hypotheses of the earlier sweep theorem. It supplies initialized subset-key records for the decomposition-search implementation. Filtering valid graph states, evaluating recurrence/DP values, deterministic geometric construction, and the complete clustering recovery program are separate obligations.
import Definitions.Def_StableMSR_ComponentGraphMemory open scoped Classical open StableMSR.Recovery StableMSR.Recovery.Compiler
theorem StableMSR.Recovery.Compiler.CatalogCompose.canonical_subset_table_program (w : ℕ) :
∃ P : MinSumFPT.Program, DeterministicProgram P ∧ P.length = 7*w+144 ∧
∀ (n k : ℕ) (d : Point n → Point n → ℝ),
∃ steps ≤ (8*w+6)*(n+1)^w+(n+1)^w*(4*(n+1)^w+11*n+11*w+
((n+1)^w+1)*(11*n+16)+47)+30,
let result := execute P n k d steps
result.halted = true ∧ result.work = steps ∧
result.queries = 0 ∧ result.tapePos = 0 ∧
result.cfg.ptrs 5 = (((n+1)^w:ℕ):ℤ) ∧
result.cfg.ptrs 2 = 2+((w+1)*(n+1)^w:ℕ)+(n:ℤ) ∧
result.imem 0 = (n:ℤ) ∧ result.imem 1 = (k:ℤ) ∧
(∀ S : Finset (Fin n), S.card ≤ w →
∃ a < (n+1)^w,
(∀ v : Fin n, result.imem
(2+((w+1)*(n+1)^w:ℕ)+(n:ℤ)+(a:ℤ)*((n:ℤ)+1)+(v.val:ℤ)) =
if v ∈ S then 1 else 0) ∧
result.imem (2+((w+1)*(n+1)^w:ℕ)+(n:ℤ)+(a:ℤ)*((n:ℤ)+1)+(n:ℤ)) = 0) ∧
result.cfg.regs = (initialStore n k).regs ∧
result.cfg.mem = (initialStore n k).mem := by sorry