Simulation theorem for relocated real-RAM programs
ProvedPNormRegLib.reloc_simmachine-modelprogram-verificationreal-ram
Let be relocation parameters and a frame forming a valid pair (definitions PNormRegLib_Reloc and PNormRegLib_Simulation), and write for the coin tape shifted by the cursor offset of . Let and be programs such that:
- embeds at offset , and uses indices below ;
- is a literal bound of (definition
PNormRegLib_AddressBound); - the host state and the virtual state are in simulation, and is -bounded with and .
If , run from on , is halted after steps, then there is such that , run from on for steps, reaches a running state at the exit label that represents the state of after steps:
In particular the host work is plus twice the virtual work, the host memory on the window is the final virtual memory, and the memory outside the window is unchanged. This is the composition theorem that lets a program known only to exist run as a subroutine of a larger program.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_PNormRegLib_AddressBound import Definitions.Def_PNormRegLib_Reloc import Definitions.Def_PNormRegLib_Simulation
Formal statement
namespace PNormRegLib
open PNormReg
/-- **Simulation theorem.** Let the host program `Q` contain the relocated copy of `P` at position
`p.cOff`, and let the real state `r` represent the running virtual state `v` (`Sim`). Suppose `v` is
`PBounded Y`, where `Y` is at least a literal bound `X ≥ 1` of `P`, and the window radius is at least
`Y · 2^t`. If `P` halts from `v` within `t` steps (on the tape shifted by `k`), then `Q` reaches from
`r` a running state at the exit label that represents the halted virtual state. -/
theorem reloc_sim (p : RelocParams) (F : Frame) (P Q : Program) (ω : ℕ → Bool) (X : ℤ)
(hE : Embeds Q (reloc p P) p.cOff) (hV : Valid p F) (hU : UsesBelow P F.nR F.nQ)
(hlit : LitBound P X) (hX : 1 ≤ X) (t : ℕ) (Y : ℤ) (r v : State) (hS : Sim p F r v)
(hB : PBounded Y v) (hXY : X ≤ Y) (hR : Y * 2 ^ t ≤ F.R)
(hh : (run P v (fun i => ω (i + F.k)) t).halted = true) :
∃ t', Agree p F (run Q r ω t') (run P v (fun i => ω (i + F.k)) t) ∧
(run Q r ω t').core.pc = p.exit ∧ (run Q r ω t').halted = false := 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.