Documentation

Complexitylib.Models.RandomAccessMachine.Simulation.RegisterStore.Machine.Lookup.Internal.Scan

Reusable sparse-register lookup -- bounded scan phase #

theorem Complexity.RAM.RegisterStore.Machine.entryLookupScan_hoareTime_internal {n : ℕ} (tapes : EntryLookupRestoreTapes n) (store : Store) (address : ℕ) (initialWork preparedWork : Fin n → Tape) (inp₀ out₀ : Tape) (hprepared : EntryLookupPrepared tapes store address initialWork preparedWork) (hinput : TM.Parked inp₀) (houtput : TM.Parked out₀) :
(entryLookupTM tapes.scan).HoareTime (fun (inp : Tape) (work : Fin n → Tape) (out : Tape) => inp = inp₀ ∧ work = preparedWork ∧ out = out₀) (fun (inp : Tape) (work : Fin n → Tape) (out : Tape) => inp = inp₀ ∧ EntryLookupScanned tapes store address initialWork preparedWork work ∧ out = out₀) (entryLookupTime tapes.scan address store)

The scanner phase preserves the reusable external ABI and packages every fact needed to copy the value and restore the scanner-owned tapes.