Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The queue-empty test is the unique transition into restoration entry

Proved
DirKECC1549.Main.reverse_search_restore_predecessor

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

graph-algorithmsword-ram

For the fixed reverseSearchAlgorithm at any word width, let s and t be machine states such that one successful step carries s to t and t has program counter 111. Then

s.pc⁡=70,s.halted⁡=false,t.mem⁡=s.mem⁡,s.\operatorname{pc}=70,\qquad s.\operatorname{halted}=\mathrm{false},\qquad t.\operatorname{mem}=s.\operatorname{mem},s.pc=70,s.halted=false,t.mem=s.mem,

and the unsigned words in queue-tail register 10 and queue-head register 9 satisfy

toNat⁡(s.mem⁡(10))≤toNat⁡(s.mem⁡(9)).\operatorname{toNat}(s.\operatorname{mem}(10))\le \operatorname{toNat}(s.\operatorname{mem}(9)).toNat(s.mem(10))≤toNat(s.mem(9)).

No graph-layout, valid-input, root, initialization, or numeric word-width assumption is needed. The assertion is about any successful single step of the actual lowered instruction list. It identifies the unique entry into the restoration epilogue and the exact queue comparison that selected it.

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_restore_predecessor (w : Width) (s t : State w)
    (hstep : step Uniform.noConstants
      (Complexity.Program.lower w reverseSearchAlgorithm.code) s = some t)
    (hpc : t.pc = 111) :
    s.pc = 70 ∧ s.halted = false ∧ t.mem = s.mem ∧
      (s.mem 10).toNat ≤ (s.mem 9).toNat := by sorry

end DirKECC1549.Main
Source
Decomposition of the restoration-entry invariant https://prove2.me/theorems/12a0367d-b08f-4e35-8f92-9049fe3034d6. Uses the explicit reverseSearchAlgorithm in Definitions.Def_DirKECC1549_Main_ReverseSearchCode: PC 70 tests register 10 <= register 9 and branches to 111; the remaining code has no transition into 111. Abstract scan histories use Definitions.Def_DirKECC1549_Main_ReverseScanTrace.

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