Documentation

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

Bounded encoded sparse-store update -- unmatched entry iteration #

theorem Complexity.RAM.RegisterStore.Machine.entryUpdateIteration_miss_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) (hne : entry.1 address) (hinput : TM.Parked inp) (houtput : out.HasBinaryPrefix (outPrefix ++ List.flatMap Entry.encode emitted)) :
∃ (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 ++ [entry]) rest (emitted ++ [entry]) found resultCount initialWork nextWork nextOut.HasBinaryPrefix (outPrefix ++ List.flatMap Entry.encode (emitted ++ [entry]))

One unmatched old entry is copied to the output, its remaining-count unit is consumed, and the update controller returns to its loop-test state.