One step of the real RAM executes the fetched instruction
ProvedPNormRegLib.step_eq_execmachine-modelprogram-verificationreal-ram
Let be a program of the real RAM PNormReg_Machine, a coin tape and a state that is not halted, and suppose the instruction of at the program counter of is . Then
where is the single-instruction semantics of the definition PNormRegLib_Exec.
This is the bridge between the machine's step function and per-instruction reasoning: once the fetched instruction is known, a step can be computed without the program.
Preamble
import Mathlib import Definitions.Def_PNormReg_Machine import Definitions.Def_PNormRegLib_Exec
Formal statement
namespace PNormRegLib
open PNormReg
/-- In a running state whose program counter holds `ins`, one step of the machine is `exec ins`. -/
theorem step_eq_exec (P : Program) (ω : ℕ → Bool) (s : State) (ins : Instr)
(hh : s.halted = false) (h : P[s.core.pc]? = some ins) : step P ω s = exec ω ins s := by sorry
end PNormRegLib
Source
Restatement of PNormReg.step (definition PNormReg_Machine) and SmaleNinth.RAMStep (definition SmaleNinth_RealRAM), split by instruction; original library definition, written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions'.