Word-RAM code relocation preserves execution and exact costs
ProvedITPIRPreproc.MatchVec.WordRAM.code_relocation_correctLet and be arbitrary finite word-RAM programs, and let . Place after , adding to every absolute jump target in . For any initial state , input, coin tape, and number of steps , execution of the relocated block from the state with program counter equals the original execution with its final program counter shifted by :
All other state fields, including accumulated work, agree exactly; hence storage at corresponding states also agrees. The combined program is deterministic exactly when both constituent programs are deterministic, and is streaming exactly when both constituents are streaming.
This lemma permits a verified code block to be placed at an arbitrary address without changing its behavior or cost. Execution starts inside the relocated block; the statement does not claim that the preceding code has been executed or that arbitrary blocks can be sequentially composed without an interface invariant.
import Definitions.Def_ITPIRPreproc_MatchVec_RAMRelocation import Mathlib.Tactic open ITPIRPreproc.MatchVec.WordRAM
theorem ITPIRPreproc.MatchVec.WordRAM.code_relocation_correct (precode P : Program) :
(Deterministic (placeAfter precode P) ↔ Deterministic precode ∧ Deterministic P) ∧
(Streaming (placeAfter precode P) ↔ Streaming precode ∧ Streaming P) ∧
∀ (inp : List Bool) (ω : ℕ → Bool) (s : State) (k : ℕ),
(step (placeAfter precode P) inp ω)^[k] (relocateState precode.length s) =
relocateState precode.length ((step P inp ω)^[k] s) := by sorry