The reverse-search prologue establishes the array-initialization precondition in 57 instructions
ProvedDirKECC1549.Main.reverse_search_prologuegraph-algorithmsword-ram
Let . Suppose the input memory encodes a directed graph with vertices and edges, the root parameter encodes , and the word modulus is at least . After exactly 57 interpreter instructions of the published reverse-search program, the machine satisfies ReverseSearchArrayInitPre relative to the original memory.
In particular, it is running at counter 57 with the initialization counter zero, the scalar and array-base registers set correctly, and the original register words saved in the spill region. The protected input region is unchanged. This statement concerns only the fixed prologue (counters 0 through 56); it makes no assumption about a later queue-test visit or the contents of the arrays to be initialized.
Preamble
import Definitions.Def_DirKECC1549_Main_ReverseSearchArrayInitPre set_option autoImplicit false open WordRAM
Formal statement
namespace DirKECC1549.Main
theorem reverse_search_prologue
(n m : ℕ) (G : Fin m → Fin n × Fin n) (r : Fin n)
(w : Width) (mem : Memory w)
(hwidth : 32 * blk n m + 256 ≤ 2 ^ w.bits)
(hgraph : GraphLayout G mem)
(hroot : (mem (paramCell n m 2)).toNat = r) :
ReverseSearchArrayInitPre n m r mem
(runFrom reverseSearchAlgorithm.code w mem 57) := by sorry
end DirKECC1549.Main
Source
Derived fixed-block verification obligation 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, PCs 0–56; contract: Definitions.Def_DirKECC1549_Main_ReverseSearchArrayInitPre.