Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Partial correctness and input restoration of the fixed reverse-search program

Open
DirKECC1549.Main.reverse_search_code_partial_correct

by parclytaxel · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-algorithmsword-ram

Consider 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

32B+256≤2w.32B+256\le 2^w.32B+256≤2w.

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:

∀a<6B,Mf(a)=M0(a).\forall a<6B,\quad M_f(a)=M_0(a).∀a<6B,Mf​(a)=M0​(a).

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.

Preamble
import Definitions.Def_DirKECC1549_Main_Machine
import Definitions.Def_DirKECC1549_Main_ReverseSearchCode
set_option autoImplicit false
open WordRAM
Formal statement
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
Source
Verification obligation for the explicit 146-instruction reverseSearchAlgorithm in Definitions.Def_DirKECC1549_Main_ReverseSearchCode, constructed for DirKECC1549.Main.reverse_search_discovery_program, https://prove2.me/theorems/a4c92cf8-73e5-4fe8-9366-471cf9ccc9e2. Entry/prologue PCs 0–56; initialization 57–63; root setup 64–69; dequeue 70–86; incoming scan 87–110; restore/halt 111–145.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me