Search-core exit state and spill invariant before the restoring epilogue
OpenDirKECC1549.Main.reverse_search_core_exitLet G be a graph with n vertices and m edges and root r, and set
Suppose initial memory M contains GraphLayout G and stores r at parameter cell 5B+2, with 32B+256 at most the word modulus. If the fixed reverseSearchAlgorithm has a halted execution from M, then some interpreter fuel reaches a running state s at program counter 111, before the restoring epilogue.
At that state register 2 contains S. The saved words reproduce the original registers:
All original words at addresses strictly above 16 and below 6B are already unchanged. Moreover, the parent array encodes a vertex-valued parent map P for which there exist a discovery list L and scanned-edge set E_s forming a ReverseScanTrace from the abstract initial state, and every edge whose head belongs to L is in E_s.
This theorem isolates the prologue, initialization, and search core before instructions 111–145. It is conditional on a halted execution and asserts neither a runtime bound nor restoration of working-register cells; the separate epilogue theorem supplies restoration.
import Definitions.Def_DirKECC1549_Main_Machine import Definitions.Def_DirKECC1549_Main_ReverseSearchCode import Definitions.Def_DirKECC1549_Main_ReverseScanTrace set_option autoImplicit false open WordRAM
namespace DirKECC1549.Main
theorem reverse_search_core_exit
(n m : ℕ) (G : Fin m → Fin n × Fin n) (r : Fin n)
(w : Width) (mem : Memory w) (fuel : ℕ)
(hwidth : 32 * blk n m + 256 ≤ 2 ^ w.bits)
(hgraph : GraphLayout G mem)
(hroot : (mem (paramCell n m 2)).toNat = r)
(hhalt : (runFrom reverseSearchAlgorithm.code w mem fuel).halted = true) :
let S := 16 * blk n m + 64
∃ steps : ℕ,
let s := runFrom reverseSearchAlgorithm.code w mem steps
s.pc = 111 ∧ s.halted = false ∧ (s.mem 2).toNat = S ∧
s.mem (S + 16) = mem 0 ∧
(∀ a : ℕ, 1 ≤ a → a ≤ 16 → s.mem (S + a - 1) = mem a) ∧
(∀ a : ℕ, 16 < a → a < 6 * blk n m → s.mem a = mem a) ∧
∃ (par : Fin n → Fin n) (order : List (Fin n)) (scanned : Finset (Fin m)),
ReverseScanTrace G r par order scanned ∧
(∀ e : Fin m, (G e).2 ∈ order → e ∈ scanned) ∧
∀ v : Fin n, (s.mem (arrayCell n m v)).toNat = par v := by sorry
end DirKECC1549.Main