Relocation preserves deterministic programs
ProvedDetANN.reloc_detProgrammachine-modelnearest-neighbor-searchprogram-verificationreal-ram
Let be relocation parameters (definition PNormRegLib_Reloc) and let be a deterministic program in the sense of DetANN.DetProgram: rational literals, no accept or reject, no coin and no real power. Then
A host program built from relocated copies of deterministic programs, together with deterministic glue code, therefore meets the determinism requirement of DetANN.theorem_1_1.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_PNormRegLib_Reloc import Definitions.Def_DetANN_DataStructure
Formal statement
namespace DetANN
/-- Relocation preserves determinism: the relocated copy of a `DetProgram` is a `DetProgram`. -/
theorem reloc_detProgram (p : PNormRegLib.RelocParams) (P : PNormReg.Program)
(hP : DetProgram P) : DetProgram (PNormRegLib.reloc p P) := by sorry
end DetANN
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.