Documentation

Complexitylib.Models.RandomAccessMachine.Simulation.RegisterStore.Machine.Instruction.Store

Indirect sparse-store instructions -- proof internals #

theorem Complexity.RAM.RegisterStore.Machine.indirectStoreInstructionTM_hoareTime_frame_internal {n : ℕ} (tapes : BinaryInstructionTapes n) (store : Store) (addressRegister source : ℕ) (emittedBits : List Bool) (initialWork : Fin n → Tape) (inp₀ out₀ : Tape) (hcanonical : Canonical store) (hinitial : EntryLookupStaticReady tapes.lhsLookup store initialWork) (hrhs₀ : (initialWork tapes.rhs).HasBinaryNat 0) (hreplacement : (initialWork tapes.update.replacement).HasBinaryNat 0) (hinput : TM.Parked inp₀) (houtput : out₀.HasBinaryPrefix emittedBits) :
(indirectStoreInstructionTM tapes addressRegister source).HoareTime (fun (inp : Tape) (work : Fin n → Tape) (out : Tape) => inp = inp₀ ∧ work = initialWork ∧ out = out₀) (fun (inp : Tape) (work : Fin n → Tape) (out : Tape) => inp = inp₀ ∧ IndirectStoreInstructionResult tapes store addressRegister source initialWork work ∧ out.HasBinaryPrefix (emittedBits ++ List.flatMap Entry.encode (write store (read store addressRegister) (read store source)))) (indirectStoreInstructionTime tapes store addressRegister source)

Exact semantic and time contract for one indirect sparse store.