The first queue-test visit occurs exactly 7n+7 instructions after prepared fuel 57
ProvedDirKECC1549.Main.reverse_search_first_queue_clockgraph-algorithmsword-ram
Let be the graph sizes, let be a vertex, and suppose the word modulus is at least . Assume that after 57 instructions the reverse-search program satisfies its array-initialization precondition relative to the original memory. Then its first running visit to the queue test at counter 70 occurs at interpreter fuel
At fuel the machine is running at counter 70, and at every smaller fuel it is not both running and at counter 70. This isolates the exact initialization-and-root-setup clock from the functional correctness of the fixed prologue.
Preamble
import Definitions.Def_DirKECC1549_Main_ReverseSearchArrayInitPre set_option autoImplicit false open WordRAM
Formal statement
namespace DirKECC1549.Main
theorem reverse_search_first_queue_clock (n m : ℕ) (r : Fin n) (w : Width) (mem : Memory w)
(hwidth : 32 * blk n m + 256 ≤ 2 ^ w.bits)
(hpre : ReverseSearchArrayInitPre n m r mem
(runFrom reverseSearchAlgorithm.code w mem 57)) :
(runFrom reverseSearchAlgorithm.code w mem (57 + (7 * n + 7))).pc = 70 ∧
(runFrom reverseSearchAlgorithm.code w mem (57 + (7 * n + 7))).halted = false ∧
∀ j < 57 + (7 * n + 7),
¬ ((runFrom reverseSearchAlgorithm.code w mem j).pc = 70 ∧
(runFrom reverseSearchAlgorithm.code w mem j).halted = false) := by sorry
end DirKECC1549.Main
Source
Derived control-flow lemma for reverse_search_first_visit_array_entry, https://prove2.me/theorems/e0e08009-38e3-45fd-8d8a-da4b57e39227. Exact source: reverseSearchAlgorithm in Definitions.Def_DirKECC1549_Main_ReverseSearchCode, straight-line PCs 0–56, seven-instruction initialization loop PCs 57–63, and root setup PCs 64–69. Uses the invariant of reverse_search_initialize_arrays, https://prove2.me/theorems/f5255df8-349b-4e54-8044-826a8fba75b9.