Documentation

Complexitylib.Models.RandomAccessMachine.Simulation.RegisterStore.Machine.EntryUpdate.Internal.Step

Bounded encoded sparse-store update -- one positive iteration #

theorem Complexity.RAM.RegisterStore.Machine.entryUpdateIteration_internal {n : ℕ} (tapes : EntryUpdateTapes n) (store : Store) (address newValue : ℕ) (processed emitted : Store) (entry : Entry) (rest : Store) (found : Bool) (resultCount : ℕ) (initialWork work : Fin n → Tape) (outPrefix : List Bool) (inp out : Tape) (hinv : EntryUpdateLoopInv tapes store address newValue processed (entry :: rest) emitted found resultCount initialWork work) (hnodup : AddressesNodup store) (hinput : TM.Parked inp) (houtput : out.HasBinaryPrefix (outPrefix ++ List.flatMap Entry.encode emitted)) :
∃ (processed' : Store) (emitted' : Store) (found' : Bool) (resultCount' : ℕ) (nextWork : Fin n → Tape) (nextOut : Tape), ∃ time ≤ entryUpdateIterationTime tapes entry rest address newValue (List.length store), (entryUpdateTM tapes).reachesIn time (entryUpdateTestCfg tapes inp work out) (entryUpdateTestCfg tapes inp nextWork nextOut) ∧ EntryUpdateLoopInv tapes store address newValue processed' rest emitted' found' resultCount' initialWork nextWork ∧ nextOut.HasBinaryPrefix (outPrefix ++ List.flatMap Entry.encode emitted')

One positive old-entry iteration advances the semantic and tape loop invariant, returning to the controller's test state.