Address bound for the real RAM
ProvedPNormRegLib.bounded_runmachine-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 ,
Since one step can at most double the largest integer in absolute value, every address a run uses within steps lies in . This explicit window is the basis for running black-box programs side by side in disjoint memory regions.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_PNormRegLib_AddressBound
Formal statement
namespace PNormRegLib
open PNormReg
/-- **Address bound.** If all pointers and integer cells of `s` are at most `X ≥ 1` in absolute
value, and so is every integer literal of `P`, then after `t` steps they are at most `X · 2^t`. -/
theorem bounded_run (P : Program) (ω : ℕ → Bool) (X : ℤ) (s : State) (hs : PBounded X s)
(hlit : LitBound P X) (hX : 1 ≤ X) (t : ℕ) : PBounded (X * 2 ^ t) (run P s ω t) := 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.