Compilation of elementary natural arithmetic into pointer instructions
ProvedStableMSR.Recovery.Compiler.BoundedSum.elementary_register_enginesalgorithmsclusteringderandomization
Constants and input projections each take one instruction. Two compiled operands in consecutive scratch registers implement addition, truncated subtraction and a comparison flag. All lower pointers and integer memory are preserved.
Preamble
import Definitions.Def_StableMSR_BoundedSumRAM open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.Compiler.BoundedSum open Polynomial
Formal statement
theorem StableMSR.Recovery.Compiler.BoundedSum.elementary_register_engines : (∀a : ℕ, Engine (fun _=>a)) ∧ (∀i : ℕ,Engine (fun ρ=>ρ i)) ∧
∀ (o : Gate) (f g : Env→ℕ), Engine f → Engine g → Engine (fun ρ=>o.val (f ρ) (g ρ)) := by
sorry
Source
Shyam Ravichandran and Lev Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Appendix B, Theorem B.2. Charged deterministic RAM implementation.