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 nTape) (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 nTape) (nextOut : Tape), timeentryUpdateIterationTime 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.