Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Fixed 146-instruction reverse breadth-first-search Word-RAM program

Definition
DirKECC1549_Main_ReverseSearchCode

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

graph-algorithmsword-ram

This defines a concrete multiplication Word-RAM algorithm with 146 instructions and polynomial capacity

capacity(N)=64(N+1)+N+16.\mathrm{capacity}(N)=64(N+1)+N+16.capacity(N)=64(N+1)+N+16.

The code implements reverse breadth-first search on the published graph layout. With B=n+2m+3, it uses the designated parent cells 6B+v, visited flags at 8B+64+v, and a queue at 10B+64+i. It initializes every parent to the vertex itself and every visited flag to zero, marks and enqueues the root, and scans each dequeued vertex's incoming-adjacency interval. A first discovery marks the predecessor, records its parent, and enqueues it.

Because the machine has no separate register file, the code first saves original cells 1 through 16 at 16B+64 through 16B+79. It reconstructs and saves original cell 0 at 16B+80. While using those cells as registers, graph reads at addresses 1 through 16 read their saved copies. The epilogue restores all cells 0 through 16 before halting.

The instruction list and its numeric jump targets are explicit. This definition contains no correctness, termination, or running-time assumption. Those properties are separate theorem obligations.

Definition code
import Definitions.Def_WordRAM_Complexity_Programs
set_option autoImplicit false

namespace DirKECC1549.Main

/-- Fixed reverse breadth-first search. Registers 0–16 are spilled and restored.
The search uses parent cells 6B+v, visited cells 8B+64+v, queue cells 10B+64+i,
and a spill area starting at 16B+64, where B = n+2m+3.
Registers: 1=n, 2=spill base, 3=m, 4=B, 5=root, 6=parent base, 7=visited base,
8=queue base, 9=head, 10=tail, 11=current vertex, 12=scan index, 13=scan end,
14=edge/predecessor, 15=visited flag. Register 0 is the indirect-address pointer.
Graph reads at addresses 1–16 use saved words while the registers are live. -/
def reverseSearchAlgorithm : WordRAM.Complexity.Algorithm .multiplication where
  capacityCoefficient := 64
  capacityDegree := 1
  code := [
    -- entry:
    -- Begin the spill prologue; input cells 0 and 1 contain n and m.
    .binary .add (.direct 0) (.memory (.direct 0)) (.memory (.direct 1)), -- 0
    .binary .add (.direct 0) (.memory (.direct 0)) (.memory (.direct 1)), -- 1
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 3), -- 2
    .binary .shl (.direct 0) (.memory (.direct 0)) (.immediate 4), -- 3
    -- Register 0 now points to spill base S = 16B+64.
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 64), -- 4
    -- Save original cell 1 at S+0.
    .copy (.indirect 0) (.memory (.direct 1)), -- 5
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 6
    -- Save original cell 2 at S+1.
    .copy (.indirect 0) (.memory (.direct 2)), -- 7
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 8
    -- Save original cell 3 at S+2.
    .copy (.indirect 0) (.memory (.direct 3)), -- 9
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 10
    -- Save original cell 4 at S+3.
    .copy (.indirect 0) (.memory (.direct 4)), -- 11
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 12
    -- Save original cell 5 at S+4.
    .copy (.indirect 0) (.memory (.direct 5)), -- 13
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 14
    -- Save original cell 6 at S+5.
    .copy (.indirect 0) (.memory (.direct 6)), -- 15
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 16
    -- Save original cell 7 at S+6.
    .copy (.indirect 0) (.memory (.direct 7)), -- 17
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 18
    -- Save original cell 8 at S+7.
    .copy (.indirect 0) (.memory (.direct 8)), -- 19
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 20
    -- Save original cell 9 at S+8.
    .copy (.indirect 0) (.memory (.direct 9)), -- 21
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 22
    -- Save original cell 10 at S+9.
    .copy (.indirect 0) (.memory (.direct 10)), -- 23
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 24
    -- Save original cell 11 at S+10.
    .copy (.indirect 0) (.memory (.direct 11)), -- 25
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 26
    -- Save original cell 12 at S+11.
    .copy (.indirect 0) (.memory (.direct 12)), -- 27
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 28
    -- Save original cell 13 at S+12.
    .copy (.indirect 0) (.memory (.direct 13)), -- 29
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 30
    -- Save original cell 14 at S+13.
    .copy (.indirect 0) (.memory (.direct 14)), -- 31
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 32
    -- Save original cell 15 at S+14.
    .copy (.indirect 0) (.memory (.direct 15)), -- 33
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 34
    -- Save original cell 16 at S+15.
    .copy (.indirect 0) (.memory (.direct 16)), -- 35
    .copy (.direct 2) (.memory (.direct 0)), -- 36
    -- Register 2 holds S throughout the search.
    .binary .sub (.direct 2) (.memory (.direct 2)) (.immediate 15), -- 37
    -- Recover m from its saved word.
    .copy (.direct 3) (.memory (.indirect 2)), -- 38
    .copy (.direct 4) (.memory (.direct 0)), -- 39
    .binary .sub (.direct 4) (.memory (.direct 4)) (.immediate 79), -- 40
    -- Recover B from S+15 = 16B+79.
    .binary .shr (.direct 4) (.memory (.direct 4)) (.immediate 4), -- 41
    .copy (.direct 1) (.memory (.direct 4)), -- 42
    .binary .sub (.direct 1) (.memory (.direct 1)) (.memory (.direct 3)), -- 43
    .binary .sub (.direct 1) (.memory (.direct 1)) (.memory (.direct 3)), -- 44
    -- Recover n from B-2m-3.
    .binary .sub (.direct 1) (.memory (.direct 1)) (.immediate 3), -- 45
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 46
    -- Save original cell 0 at S+16 for the epilogue.
    .copy (.indirect 0) (.memory (.direct 1)), -- 47
    .binary (.mul rfl) (.direct 0) (.memory (.direct 4)) (.immediate 5), -- 48
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 2), -- 49
    -- Read root r from parameter cell 5B+2, which is above register 16.
    .copy (.direct 5) (.memory (.indirect 0)), -- 50
    -- Parent-array base 6B.
    .binary (.mul rfl) (.direct 6) (.memory (.direct 4)) (.immediate 6), -- 51
    .binary (.mul rfl) (.direct 7) (.memory (.direct 4)) (.immediate 8), -- 52
    -- Visited-array base 8B+64.
    .binary .add (.direct 7) (.memory (.direct 7)) (.immediate 64), -- 53
    .binary (.mul rfl) (.direct 8) (.memory (.direct 4)) (.immediate 10), -- 54
    -- Queue base 10B+64.
    .binary .add (.direct 8) (.memory (.direct 8)) (.immediate 64), -- 55
    .copy (.direct 11) (.immediate 0), -- 56
    -- initialize:
    -- Initialize every parent and every visited flag.
    .branch .le (.memory (.direct 1)) (.memory (.direct 11)) 64, -- 57
    .binary .add (.direct 0) (.memory (.direct 6)) (.memory (.direct 11)), -- 58
    .copy (.indirect 0) (.memory (.direct 11)), -- 59
    .binary .add (.direct 0) (.memory (.direct 7)) (.memory (.direct 11)), -- 60
    .copy (.indirect 0) (.immediate 0), -- 61
    .binary .add (.direct 11) (.memory (.direct 11)) (.immediate 1), -- 62
    .jump 57, -- 63
    -- root:
    .binary .add (.direct 0) (.memory (.direct 7)) (.memory (.direct 5)), -- 64
    -- Mark the root before enqueueing it.
    .copy (.indirect 0) (.immediate 1), -- 65
    .copy (.direct 0) (.memory (.direct 8)), -- 66
    .copy (.indirect 0) (.memory (.direct 5)), -- 67
    -- Queue head.
    .copy (.direct 9) (.immediate 0), -- 68
    -- Queue tail.
    .copy (.direct 10) (.immediate 1), -- 69
    -- dequeue:
    -- Stop when the queue is empty.
    .branch .le (.memory (.direct 10)) (.memory (.direct 9)) 111, -- 70
    .binary .add (.direct 0) (.memory (.direct 8)) (.memory (.direct 9)), -- 71
    -- Current vertex u.
    .copy (.direct 11) (.memory (.indirect 0)), -- 72
    .binary .add (.direct 9) (.memory (.direct 9)) (.immediate 1), -- 73
    .binary (.mul rfl) (.direct 0) (.memory (.direct 4)) (.immediate 3), -- 74
    .binary .add (.direct 0) (.memory (.direct 0)) (.memory (.direct 11)), -- 75
    -- Read the spill copy for graph addresses 1 through 16.
    .branch .lt (.immediate 16) (.memory (.direct 0)) 79, -- 76
    .binary .add (.direct 0) (.memory (.direct 2)) (.memory (.direct 0)), -- 77
    .binary .sub (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 78
    -- begin_load:
    .copy (.direct 12) (.memory (.indirect 0)), -- 79
    .binary (.mul rfl) (.direct 0) (.memory (.direct 4)) (.immediate 3), -- 80
    .binary .add (.direct 0) (.memory (.direct 0)) (.memory (.direct 11)), -- 81
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 82
    -- Read the spill copy for graph addresses 1 through 16.
    .branch .lt (.immediate 16) (.memory (.direct 0)) 86, -- 83
    .binary .add (.direct 0) (.memory (.direct 2)) (.memory (.direct 0)), -- 84
    .binary .sub (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 85
    -- end_load:
    .copy (.direct 13) (.memory (.indirect 0)), -- 86
    -- scan:
    -- Scan the incoming-adjacency interval of u.
    .branch .le (.memory (.direct 13)) (.memory (.direct 12)) 70, -- 87
    .binary (.mul rfl) (.direct 0) (.memory (.direct 4)) (.immediate 4), -- 88
    .binary .add (.direct 0) (.memory (.direct 0)) (.memory (.direct 12)), -- 89
    -- Read the spill copy for graph addresses 1 through 16.
    .branch .lt (.immediate 16) (.memory (.direct 0)) 93, -- 90
    .binary .add (.direct 0) (.memory (.direct 2)) (.memory (.direct 0)), -- 91
    .binary .sub (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 92
    -- edge_load:
    .copy (.direct 14) (.memory (.indirect 0)), -- 93
    .binary .add (.direct 12) (.memory (.direct 12)) (.immediate 1), -- 94
    .binary (.mul rfl) (.direct 0) (.memory (.direct 14)) (.immediate 2), -- 95
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 2), -- 96
    -- Read the spill copy for graph addresses 1 through 16.
    .branch .lt (.immediate 16) (.memory (.direct 0)) 100, -- 97
    .binary .add (.direct 0) (.memory (.direct 2)) (.memory (.direct 0)), -- 98
    .binary .sub (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 99
    -- tail_load:
    .copy (.direct 14) (.memory (.indirect 0)), -- 100
    .binary .add (.direct 0) (.memory (.direct 7)) (.memory (.direct 14)), -- 101
    .copy (.direct 15) (.memory (.indirect 0)), -- 102
    -- Skip an already discovered predecessor.
    .branch .eq (.memory (.direct 15)) (.immediate 1) 87, -- 103
    -- Mark new predecessor v.
    .copy (.indirect 0) (.immediate 1), -- 104
    .binary .add (.direct 0) (.memory (.direct 6)) (.memory (.direct 14)), -- 105
    -- Set par(v) = u.
    .copy (.indirect 0) (.memory (.direct 11)), -- 106
    .binary .add (.direct 0) (.memory (.direct 8)) (.memory (.direct 10)), -- 107
    -- Enqueue v exactly once.
    .copy (.indirect 0) (.memory (.direct 14)), -- 108
    .binary .add (.direct 10) (.memory (.direct 10)) (.immediate 1), -- 109
    .jump 87, -- 110
    -- restore:
    -- Restore original cells 1 through 16, using only pointer register 0.
    .copy (.direct 0) (.memory (.direct 2)), -- 111
    .copy (.direct 1) (.memory (.indirect 0)), -- 112
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 113
    .copy (.direct 2) (.memory (.indirect 0)), -- 114
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 115
    .copy (.direct 3) (.memory (.indirect 0)), -- 116
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 117
    .copy (.direct 4) (.memory (.indirect 0)), -- 118
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 119
    .copy (.direct 5) (.memory (.indirect 0)), -- 120
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 121
    .copy (.direct 6) (.memory (.indirect 0)), -- 122
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 123
    .copy (.direct 7) (.memory (.indirect 0)), -- 124
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 125
    .copy (.direct 8) (.memory (.indirect 0)), -- 126
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 127
    .copy (.direct 9) (.memory (.indirect 0)), -- 128
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 129
    .copy (.direct 10) (.memory (.indirect 0)), -- 130
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 131
    .copy (.direct 11) (.memory (.indirect 0)), -- 132
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 133
    .copy (.direct 12) (.memory (.indirect 0)), -- 134
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 135
    .copy (.direct 13) (.memory (.indirect 0)), -- 136
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 137
    .copy (.direct 14) (.memory (.indirect 0)), -- 138
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 139
    .copy (.direct 15) (.memory (.indirect 0)), -- 140
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 141
    .copy (.direct 16) (.memory (.indirect 0)), -- 142
    .binary .add (.direct 0) (.memory (.direct 0)) (.immediate 1), -- 143
    -- Restore original n in cell 0 from S+16.
    .copy (.direct 0) (.memory (.indirect 0)), -- 144
    .halt -- 145
  ]

end DirKECC1549.Main
Source
Constructed implementation of the reverse breadth-first search obligation in DirKECC1549.Main.reverse_search_discovery_program, https://prove2.me/theorems/a4c92cf8-73e5-4fe8-9366-471cf9ccc9e2; uses the published WordRAM.Complexity instruction semantics and DirKECC1549.Main graph layout.

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