Bounded pointers and literal bounds for the real RAM
DefinitionPNormRegLib_AddressBoundmachine-modelprogram-verificationreal-ram
Consider the real RAM of the definition PNormReg_Machine, with integer pointer registers and integer memory .
- For , a state is -bounded if
- A program has literal bound if every integer constant of an instruction of satisfies .
The machine has no pointer multiplication and no conversion from reals to integers. Its integers are therefore built from literals, inputs and earlier integers by addition and subtraction only, and these two quantities control every integer value, and hence every memory address, a run can produce.
Formalization Note. PBounded X s and LitBound P L.
Definition code
import Mathlib import Definitions.Def_PNormReg_Machine namespace PNormRegLib open PNormReg /-- Every pointer register and every integer-memory cell of `s` has absolute value at most `X`. -/ def PBounded (X : ℤ) (s : State) : Prop := (∀ q, |s.core.ptrs q| ≤ X) ∧ ∀ z, |s.integerMemory z| ≤ X /-- Every integer literal of `P` (the constant `c` of an instruction `pset q c`) has absolute value at most `L`. -/ def LitBound (P : Program) (L : ℤ) : Prop := ∀ q c, Instr.core (.pset q c) ∈ P → |c| ≤ L 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.