A fixed-width bounded-subset encoding program with polynomial charged time
ProvedStableMSR.Recovery.Compiler.TupleEnumeration.bounded_subset_enumerator_programFor every fixed width , there is one deterministic program, chosen before the input size and oracle, with exactly instructions. On every input size and integer input parameter , it halts after at most
charged interpreter steps, making no distance queries and reading no random tape. It reads from the standard input memory and writes a positive-address scratch catalog beginning at address . Reading the fixed-width records gives exactly the lexicographic list of all words of length over digits . With zero treated as padding and digit representing vertex , the decoded records cover exactly all subsets of of cardinality at most ; different records may decode to the same subset. The output pointer ends at . Input cells , real memory, and integer memory outside the catalog are preserved, and charged work equals the executed instruction count.
The theorem includes and . It is a concrete internal enumeration kernel in the recovery interpreter, not the complete clustering algorithm or the canonical negative-address clustering-output format.
import Definitions.Def_StableMSR_BoundedWordCatalog open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.Compiler.TupleEnumeration
theorem StableMSR.Recovery.Compiler.TupleEnumeration.bounded_subset_enumerator_program (w : ℕ) :
∃ P : MinSumFPT.Program, DeterministicProgram P ∧ P.length = 7*w+7 ∧
∀ (n k : ℕ) (d : Point n → Point n → ℝ),
∃ steps ≤ (8*w+2)*(n+1)^w+5,
let result := execute P n k d steps
result.halted = true ∧ result.work = steps ∧
result.queries = 0 ∧ result.tapePos = 0 ∧
result.cfg.ptrs (w+1) = 2+((w+1)*(n+1)^w : ℕ) ∧
result.imem 0 = (n : ℤ) ∧ result.imem 1 = (k : ℤ) ∧
catalogWords n w result.imem = BoundedSubsetWords.words n w ∧
(∀ S : Finset (Fin n), S.card ≤ w ↔
∃ j < (n+1)^w,
BoundedSubsetWords.decode n
(readWord w result.imem (2+((w+1)*j : ℕ))) = S) ∧
(∀ a : ℤ, a < 2 ∨ 2+((w+1)*(n+1)^w : ℕ) ≤ a →
result.imem a = (initialStore n k).imem a) ∧
result.cfg.mem = (initialStore n k).mem := by sorry