The relocated halt jumps to the exit label
ProvedPNormRegLib.sim_haltmachine-modelprogram-verificationreal-ram
Let be relocation parameters and a frame (definitions PNormRegLib_Reloc and PNormRegLib_Simulation), and write for the coin tape shifted by the cursor offset of . Suppose the host state represents the virtual state , and let
Then represents , the program counter of is the exit label , the halted flag of is that of , and is halted.
This is the last step of the simulation theorem PNormRegLib.reloc_sim: where the copied program stops, the host continues at the exit label.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_PNormRegLib_Exec import Definitions.Def_PNormRegLib_Reloc import Definitions.Def_PNormRegLib_Simulation
Formal statement
namespace PNormRegLib
open PNormReg
/-- **The relocated `halt`.** If `r` represents `v`, then executing the relocated pair of `halt` on
`r` reaches the exit label without halting, while `halt` halts `v`; `Agree` is preserved. -/
theorem sim_halt (p : RelocParams) (F : Frame) (ω : ℕ → Bool) (r v : State)
(hA : Agree p F r v) :
Agree p F (exec ω (p.pair .halt).2 (exec ω (p.pair .halt).1 r))
(exec (fun i => ω (i + F.k)) .halt v) ∧
(exec ω (p.pair .halt).2 (exec ω (p.pair .halt).1 r)).core.pc = p.exit ∧
(exec ω (p.pair .halt).2 (exec ω (p.pair .halt).1 r)).halted = r.halted ∧
(exec (fun i => ω (i + F.k)) .halt v).halted = true := 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.