Prepared scalar registers, spills, and cleared arrays before root setup
DefinitionDirKECC1549_Main_ReverseSearchRootSetupPreThis predicate describes a prepared state s at program counter 64, before the fixed reverse-search program marks and enqueues its root. It is parameterized by n, m, root r, and original memory M, and does not assert that any execution reaches such a state.
Put
The state is running. The decoded values of registers 1, 3, 4, 5, 6, 7, 8, and 2 are n, m, B, r, 6B, V, Q, and S, respectively. The spill words at S through S+15 hold the original cells 1 through 16, and S+16 holds the original cell 0. Every original word at an address strictly above 16 and below 6B is unchanged.
The parent array is the identity and all visited flags are zero:
No condition is imposed on the queue contents, the head and tail registers, or unused scratch memory. This is the precondition for verifying the concrete six-instruction root-setup block at counters 64–69; establishing it from the graph input is a separate prefix-verification obligation.
import Definitions.Def_DirKECC1549_Main_Machine
import Definitions.Def_DirKECC1549_Main_ReverseSearchCode
set_option autoImplicit false
open WordRAM
namespace DirKECC1549.Main
/-- State immediately before root marking and enqueueing: scalar registers and
spill words are ready, parents are the identity, and all visited flags are zero. -/
structure ReverseSearchRootSetupPre (n m : ℕ) (r : Fin n) {w : Width}
(initial : Memory w) (s : State w) : Prop where
pc_eq : s.pc = 64
running : s.halted = false
registers :
(s.mem 1).toNat = n ∧ (s.mem 3).toNat = m ∧ (s.mem 4).toNat = blk n m ∧
(s.mem 5).toNat = r ∧ (s.mem 6).toNat = 6 * blk n m ∧
(s.mem 7).toNat = 8 * blk n m + 64 ∧ (s.mem 8).toNat = 10 * blk n m + 64
spill_pointer : (s.mem 2).toNat = 16 * blk n m + 64
saved_zero : s.mem (16 * blk n m + 64 + 16) = initial 0
saved_registers : ∀ a : ℕ, 1 ≤ a → a ≤ 16 →
s.mem (16 * blk n m + 64 + a - 1) = initial a
input_frame : ∀ a : ℕ, 16 < a → a < 6 * blk n m → s.mem a = initial a
parents_identity : ∀ v : Fin n, (s.mem (arrayCell n m v)).toNat = v
visited_zero : ∀ v : Fin n, (s.mem (8 * blk n m + 64 + v)).toNat = 0
end DirKECC1549.Main