The first queue-test visit factors through scalar/spill preparation at counter 57
ProvedDirKECC1549.Main.reverse_search_first_visit_array_entryLet original memory M satisfy GraphLayout G for n vertices and m edges and encode root r at parameter cell 5B+2, with B=n+2m+3 and 32B+256 at most the word modulus. Suppose fuel f gives the first running visit to counter 70 of reverseSearchAlgorithm.
Then there is interpreter fuel p such that
and the state after p units of fuel satisfies ReverseSearchArrayInitPre for n, m, r, and original memory M. It is running at counter 57 with correct scalar/base registers, saved original input words, the protected input region, and a zero initialization counter. No correct contents of the parent or visited arrays are included in this precondition.
This isolates the scalar/spill prologue and first-visit timing before the verified array-initialization loop and six-instruction root-setup block. The remaining 7n+7 units of fuel consist of 7n+1 for array initialization and six for root setup. The statement assumes no future halt or asymptotic running-time bound.
import Definitions.Def_DirKECC1549_Main_ReverseSearchArrayInitPre set_option autoImplicit false open WordRAM
namespace DirKECC1549.Main
theorem reverse_search_first_visit_array_entry
(n m : ℕ) (G : Fin m → Fin n × Fin n) (r : Fin n)
(w : Width) (mem : Memory w) (steps : ℕ)
(hwidth : 32 * blk n m + 256 ≤ 2 ^ w.bits)
(hgraph : GraphLayout G mem)
(hroot : (mem (paramCell n m 2)).toNat = r)
(hpc : (runFrom reverseSearchAlgorithm.code w mem steps).pc = 70)
(hrunning : (runFrom reverseSearchAlgorithm.code w mem steps).halted = false)
(hfirst : ∀ j < steps,
¬ ((runFrom reverseSearchAlgorithm.code w mem j).pc = 70 ∧
(runFrom reverseSearchAlgorithm.code w mem j).halted = false)) :
∃ fuel₀ : ℕ, steps = fuel₀ + (7 * n + 7) ∧
ReverseSearchArrayInitPre n m r mem
(runFrom reverseSearchAlgorithm.code w mem fuel₀) := by sorry
end DirKECC1549.Main