Partial correctness and input restoration of the fixed reverse-search program
OpenDirKECC1549.Main.reverse_search_code_partial_correctConsider the explicit 146-instruction multiplication Word-RAM program reverseSearchAlgorithm on a graph G with n vertices and m edges, root r, and block length B=n+2m+3. Suppose its initial memory contains GraphLayout G and the root in parameter cell 5B+2, and the word width satisfies
If the execution from that memory is halted after any interpreter fuel f, its final memory agrees with the original memory at every address below 6B:
Furthermore, the designated parent array encodes a valid vertex-valued parent map par and admits a finite list L of distinct discovered vertices. The root is its own parent and belongs to L. The list is closed under incoming edges. Every non-root vertex in L has an original graph edge to its parent, and that parent belongs to the prefix of L before the vertex's first occurrence.
This is partial correctness of a specified instruction list, including exact restoration of the input cells used as working registers. It does not assert termination or a tick bound, and places no assumptions on other initial memory words or the scalar parameters not used by the program.
import Definitions.Def_DirKECC1549_Main_Machine import Definitions.Def_DirKECC1549_Main_ReverseSearchCode set_option autoImplicit false open WordRAM
namespace DirKECC1549.Main
theorem reverse_search_code_partial_correct
(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)), par r = r ∧
order.Nodup ∧ r ∈ order ∧
(∀ e : Fin m, (G e).2 ∈ order → (G e).1 ∈ order) ∧
(∀ v ∈ order, v ≠ r →
(∃ e, G e = (v, par v)) ∧ par v ∈ order.take (order.idxOf v)) ∧
∀ v : Fin n,
((runFrom reverseSearchAlgorithm.code w mem fuel).mem (arrayCell n m v)).toNat =
par v := by sorry
end DirKECC1549.Main