Uniform native interpretation of a complete source-RAM run
ProvedLax455465Proofs.RamVirtualExecution.execute_spec_nativealgorithmscomputational-complexitygraph-theory
Let be a finite source RAM program, a finite input-word list, and the source state reached after steps at word width . Suppose the next source step is halting, input words and program literals fit the published host guards, and . From a stored input prefix, width and sufficient address/value/output buffers, the fixed native interpreter executes to a representation of , with its running flag zero, in at most
instructions. This reproduces an actual source run from zero source memory; the native buffers may initially contain stale entries.
Preamble
import Definitions.Def_EdgeSublinearMWIS_Main_NativeBlockInterfaces namespace Lax455465Proofs.RamVirtualExecution end Lax455465Proofs.RamVirtualExecution
Formal statement
theorem Lax455465Proofs.RamVirtualExecution.execute_spec_native : ∀ (B w k : Nat) (p : Lax808846.Ram.Program) (input : List Nat) (f : Lax455465Proofs.SparseRam.SparseState),
@LT.lt Nat instLTNat
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat) (@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(@HPow.hPow Nat Nat Nat (@instHPow Nat Nat (@NPow.toPow Nat (@Monoid.toNPow Nat Nat.instMonoid)))
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2))) w)
(@OfNat.ofNat Nat (nat_lit 2) (instOfNatNat (nat_lit 2)))))
(@OfNat.ofNat Nat (nat_lit 3) (instOfNatNat (nat_lit 3))))
B →
@LT.lt Nat instLTNat
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) k (@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
B →
@LT.lt Nat instLTNat
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) (@List.length Lax808846.Ram.Instr p)
(@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
B →
(∀ (i : Lax808846.Ram.Instr),
@Membership.mem Lax808846.Ram.Instr Lax808846.Ram.Program (@List.instMembership Lax808846.Ram.Instr) p i →
Lax455465Proofs.RamVirtualInstruction.LiteralsFit
(@HSub.hSub Nat Nat Nat (@instHSub Nat instSubNat) B
(@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
i) →
@LT.lt Nat instLTNat (@List.length Nat input) B →
(∀ (x : Nat),
@Membership.mem Nat (List Nat) (@List.instMembership Nat) input x → @LT.lt Nat instLTNat x B) →
@Eq (Option Lax455465Proofs.SparseRam.SparseState)
(Lax455465Proofs.SparseRam.run w p k (Lax455465Proofs.SparseRam.init input))
(@Option.some Lax455465Proofs.SparseRam.SparseState f) →
@Eq (Option Lax455465Proofs.SparseRam.SparseState) (Lax455465Proofs.SparseRam.step w p f)
(@Option.none Lax455465Proofs.SparseRam.SparseState) →
Lax808846Proofs.Reasoning.Spec B
(fun (σ : Lax808846Proofs.Imp.Env) =>
And (@Eq Nat (σ.vars "vm.width") w)
(And (Lax455465Proofs.RamVirtualState.Prefix input "vm.input" σ)
(And (@Eq Nat (σ.vars "vm.inputLength") (@List.length Nat input))
(And (@LT.lt Nat instLTNat k (@List.length Nat (σ.arrs "vm.addresses")))
(And (@LT.lt Nat instLTNat k (@List.length Nat (σ.arrs "vm.values")))
(@LT.lt Nat instLTNat k (@List.length Nat (σ.arrs "vm.output"))))))))
(Lax455465Proofs.RamVirtualProgram.execute p)
(fun (x τ : Lax808846Proofs.Imp.Env) =>
And (Lax455465Proofs.RamVirtualState.Represents w f τ)
(@Eq Nat (τ.vars "vm.running") (@OfNat.ofNat Nat (nat_lit 0) (instOfNatNat (nat_lit 0)))))
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat) k
(@OfNat.ofNat Nat (nat_lit 1) (instOfNatNat (nat_lit 1))))
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HAdd.hAdd Nat Nat Nat (@instHAdd Nat instAddNat)
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 4) (instOfNatNat (nat_lit 4)))
(@List.length Lax808846.Ram.Instr p))
(@HMul.hMul Nat Nat Nat (@instHMul Nat instMulNat)
(@OfNat.ofNat Nat (nat_lit 32) (instOfNatNat (nat_lit 32))) k))
(@OfNat.ofNat Nat (nat_lit 104) (instOfNatNat (nat_lit 104)))))
(@OfNat.ofNat Nat (nat_lit 18) (instOfNatNat (nat_lit 18)))) := by sorrySource