Halted executions of the fixed reverse-search code refine completed abstract scans
OpenDirKECC1549.Main.reverse_search_code_refines_scanConsider the fixed 146-instruction reverseSearchAlgorithm on a graph G with n vertices and m edges and a root r. Put B=n+2m+3. Suppose the initial memory M contains GraphLayout G and stores r at parameter cell 5B+2. Assume the word width satisfies
If execution from M is halted after interpreter fuel f, its final memory agrees with M at every address below 6B. Moreover, there exist a vertex-valued parent map P, a discovery list L, and a scanned-edge set S such that the final state is represented by a finite ReverseScanTrace from identity parents, list [r], and the empty edge set. All edges entering discovered vertices have been scanned:
For every vertex v, the designated parent-array cell in the final memory encodes P(v). The theorem applies to every halted run, including runs supplied excess interpreter fuel after the halt. Other initial memory words are arbitrary.
This is a refinement and input-restoration obligation for the concrete instruction list. It has no runtime or termination conclusion, and it assumes no separate discovery-list or parent-correctness certificate. Those abstract consequences are obtained from the trace invariants.
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_code_refines_scan
(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) :
(∀ a < 6 * blk n m,
(runFrom reverseSearchAlgorithm.code w mem fuel).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,
((runFrom reverseSearchAlgorithm.code w mem fuel).mem (arrayCell n m v)).toNat =
par v := by sorry
end DirKECC1549.Main