Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The first queue-test visit occurs exactly 7n+7 instructions after prepared fuel 57

Proved
DirKECC1549.Main.reverse_search_first_queue_clock

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

graph-algorithmsword-ram

Let n,mn,mn,m be the graph sizes, let rrr be a vertex, and suppose the word modulus is at least 32(n+2m+3)+25632(n+2m+3)+25632(n+2m+3)+256. Assume that after 57 instructions the reverse-search program satisfies its array-initialization precondition relative to the original memory. Then its first running visit to the queue test at counter 70 occurs at interpreter fuel

N=57+(7n+7).N=57+(7n+7).N=57+(7n+7).

At fuel NNN the machine is running at counter 70, and at every smaller fuel it is not both running and at counter 70. This isolates the exact initialization-and-root-setup clock from the functional correctness of the fixed prologue.

Preamble
import Definitions.Def_DirKECC1549_Main_ReverseSearchArrayInitPre
set_option autoImplicit false
open WordRAM

Formal statement
namespace DirKECC1549.Main

theorem reverse_search_first_queue_clock (n m : ℕ) (r : Fin n) (w : Width) (mem : Memory w)
    (hwidth : 32 * blk n m + 256 ≤ 2 ^ w.bits)
    (hpre : ReverseSearchArrayInitPre n m r mem
      (runFrom reverseSearchAlgorithm.code w mem 57)) :
    (runFrom reverseSearchAlgorithm.code w mem (57 + (7 * n + 7))).pc = 70 ∧
    (runFrom reverseSearchAlgorithm.code w mem (57 + (7 * n + 7))).halted = false ∧
    ∀ j < 57 + (7 * n + 7),
      ¬ ((runFrom reverseSearchAlgorithm.code w mem j).pc = 70 ∧
        (runFrom reverseSearchAlgorithm.code w mem j).halted = false) := by sorry

end DirKECC1549.Main
Source
Derived control-flow lemma for reverse_search_first_visit_array_entry, https://prove2.me/theorems/e0e08009-38e3-45fd-8d8a-da4b57e39227. Exact source: reverseSearchAlgorithm in Definitions.Def_DirKECC1549_Main_ReverseSearchCode, straight-line PCs 0–56, seven-instruction initialization loop PCs 57–63, and root setup PCs 64–69. Uses the invariant of reverse_search_initialize_arrays, https://prove2.me/theorems/f5255df8-349b-4e54-8044-826a8fba75b9.

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