Spill and completed-scan invariant at reachable restoration entry
OpenDirKECC1549.Main.reverse_search_at_restore_invariantLet G be a directed multigraph with n vertices and m edges and a root r. Put
Suppose initial memory M satisfies GraphLayout G and stores r at parameter cell 5B+2, and that 32B+256 is at most the word modulus. If running the fixed reverseSearchAlgorithm from that input for some interpreter fuel reaches a still-running state s with program counter 111, then register 2 contains S and the spill words preserve the original registers:
Every original word strictly above address 16 and below 6B is unchanged. The parent array at state s encodes a vertex-valued parent map P, and there exist a discovery list L and scanned-edge set E_s forming a ReverseScanTrace from identity parents, the singleton root list, and the empty edge set. The trace is complete for incoming edges of discovered vertices:
The assertion is an invariant of reachable restoration-entry states, not of arbitrary states at counter 111. It does not assume a later halt and does not assert that such a state is reached, a runtime bound, or restoration of the working-register cells themselves.
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_at_restore_invariant
(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 = 111)
(hrunning : (runFrom reverseSearchAlgorithm.code w mem steps).halted = false) :
let S := 16 * blk n m + 64
let s := runFrom reverseSearchAlgorithm.code w mem steps
(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