Locality of real-RAM runs
ProvedPNormRegLib.run_mem_outsidemachine-modelprogram-verificationreal-ram
Let be a program of the real RAM PNormReg_Machine, let be a coin tape, let be an integer, and let be an -bounded state (definition PNormRegLib_AddressBound) such that is also a literal bound for . Write for the state after steps of from on . Then for every and every address with ,
where is the real memory and the integer memory.
A run of steps therefore leaves all memory outside the window untouched, which is the frame property needed to compose programs.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_PNormRegLib_AddressBound
Formal statement
namespace PNormRegLib
open PNormReg
/-- **Locality.** Under the hypotheses of `bounded_run`, a run of `t` steps leaves every real and
every integer memory cell at an address `y` with `|y| > X · 2^t` unchanged. -/
theorem run_mem_outside (P : Program) (ω : ℕ → Bool) (X : ℤ) (s : State) (hs : PBounded X s)
(hlit : LitBound P X) (hX : 1 ≤ X) (t : ℕ) (y : ℤ) (hy : X * 2 ^ t < |y|) :
(run P s ω t).core.mem y = s.core.mem y ∧
(run P s ω t).integerMemory y = s.integerMemory y := by sorry
end PNormRegLib
Source
Original library result for the PNormReg machine (definition PNormReg_Machine: Adil, Bullins, O'Carroll, Sidford, Solving p-norm regression in matrix multiplication time, STOC 2027 submission), written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions' at the captain's invitation (mission discussion, 2026-11-14). No external source is claimed; the doubling argument is the standard one for machines whose only integer arithmetic is addition and subtraction.