Every real-RAM program uses finitely many registers
ProvedPNormRegLib.exists_usesBelowmachine-modelprogram-verificationreal-ram
For every program of the real RAM PNormReg_Machine there is such that
that is, uses indices below in the sense of the definition PNormRegLib_Reloc.
This supplies the index bounds of a frame for a program that is only known to exist.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_PNormRegLib_Reloc
Formal statement
namespace PNormRegLib /-- Every program uses only finitely many register and pointer indices: there is `n` with all of them below `n`. -/ theorem exists_usesBelow (P : PNormReg.Program) : ∃ n : ℕ, UsesBelow P n n := 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; relocating a program by shifting its jump targets and memory accesses is the standard technique for composing machine programs.