Uniform linear tick bound for the fixed reverse-search program
OpenDirKECC1549.Main.reverse_search_code_terminatesLet G be any finite directed multigraph with n vertices and m edges, and let r be a vertex. Set B=n+2m+3. Suppose the initial memory contains the published graph layout and stores r in parameter cell 5B+2. For every word width satisfying
the explicit 146-instruction multiplication Word-RAM program reverseSearchAlgorithm successfully halts, and some interpreter fuel yields a halted state with
All memory outside the required graph and root layout is arbitrary initially. Loops, parallel edges, unreachable vertices, and single-vertex graphs are allowed. There is no requirement that every vertex reach the root, and the program need not initialize or inspect unused scratch cells.
This theorem isolates termination and a concrete instruction-count bound for a specified instruction list. It makes no assertion about the final parent certificate or preservation of the input; those are separate partial-correctness obligations.
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_terminates
(n m : ℕ) (G : Fin m → Fin n × Fin n) (r : Fin n)
(w : Width) (mem : Memory w)
(hwidth : 32 * blk n m + 256 ≤ 2 ^ w.bits)
(hgraph : GraphLayout G mem)
(hroot : (mem (paramCell n m 2)).toNat = r) :
∃ fuel : ℕ,
(runFrom reverseSearchAlgorithm.code w mem fuel).halted = true ∧
(runFrom reverseSearchAlgorithm.code w mem fuel).ticks ≤ 256 * (m + n) := by sorry
end DirKECC1549.Main