Straight-line segments of the BSP construction block: init, dispatch and scan
ProvedDetANN.HPIM.BD.scan_stepsapproximate-nearest-neighborcomputational-geometrydata-structures
Twenty-three straight-line facts about the program of definition DetANN_HPIMBuildProg: the start, the task dispatch, the end and the point scan.
Every conjunct has the same shape. Let contain at offset (Embeds Q (bd off) off), and let be a non-halted state at the stated pc with pointer 1 and the stated hypotheses. Then after exactly the stated number of steps, the run of from :
- is at the stated pc (relative to ) and has not halted;
- has the stated values in the changed registers and cells;
- leaves all other pointer and real registers and all other real and integer cells unchanged;
- has work , and its
cellsWrittenset consists of the listed cells.
Pointer 1 holds , pointer 11 holds , and , denote pointers 13, 14 of .
- Init (13 steps): pointer , , , ; reals , , , , , (with = reals 11, 12); pointers (the root box), .
- Copy step (7): when ( = pointer 46), real cell gets the value of , and .
- Copy exit (1): when .
- Root task (14): pointers (the root slot), and the entry is pushed at ; pointers .
- Empty stack (1): when pointer pointer 42.
- End (1): pointer .
- Pop (11): when the stack pointer (pointer 42) satisfies : pointers , , ; the near box : pointers ; flag , index .
- Scan exit (1): when ( = pointer 45).
- Scan head (8): pointer 47 := the address of point ; reals ; .
- Distance exit (1): when .
- Distance step (33): adds the -th terms of both squared distances (point at pointer 47, box at pointer 43) to reals 42, 43; .
- Far (3): when real real 40 (which holds under
Env). - Good (4): when real real 40 and real real 41 ().
- Near, update (6): when near, not good, and the flag (pointer 49) exceeds pointer 69 (0).
- Near, first (6): when near, not good, and the flag is at most pointer 69.
- Update exit (1).
- Update step (23): coordinate of becomes for the point .
- First step (9): coordinate of becomes .
- First exit (2): flag .
- Next point (2): .
- Certified leaf (3): pointer .
- No near point (2): when the flag is 0: pointer .
- Near points (3): when the flag is 1: pointers , .
Preamble
import Mathlib import Definitions.Def_DetANN_HPIMBuildProg import Definitions.Def_PNormReg_Machine import Definitions.Def_PNormRegLib_Exec import Definitions.Def_DetANN_DataStructure import Definitions.Def_PNormRegLib_Reloc import Definitions.Def_DetANN_HPIMBuild import Definitions.Def_DetANN_HPIMPreBlocks
Formal statement
namespace DetANN.HPIM.BD
open PNormReg PNormRegLib DetANN DetANN.HPIM
theorem scan_steps :
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 0) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 13).core.pc = off + 13 ∧ (run Q s detTape 13).halted = false ∧ (run Q s detTape 13).core.ptrs 14 = s.core.ptrs 14 - 2 * s.core.ptrs 1 ∧ (run Q s detTape 13).core.ptrs 40 = s.core.ptrs 13 ∧ (run Q s detTape 13).core.ptrs 43 = s.core.ptrs 14 - 2 * s.core.ptrs 1 ∧ (run Q s detTape 13).core.ptrs 46 = 0 ∧ (run Q s detTape 13).core.ptrs 60 = 2 * s.core.ptrs 1 ∧ (run Q s detTape 13).core.ptrs 68 = 1 ∧ (run Q s detTape 13).core.ptrs 69 = 0 ∧ (∀ x, x ≠ 14 → x ≠ 40 → x ≠ 43 → x ≠ 46 → x ≠ 60 → x ≠ 68 → x ≠ 69 → (run Q s detTape 13).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 13).core.regs 40 = (s.core.regs 11 * s.core.regs 11) ∧ (run Q s detTape 13).core.regs 41 = ((s.core.regs 12 * s.core.regs 11) * (s.core.regs 12 * s.core.regs 11)) ∧ (run Q s detTape 13).core.regs 47 = (s.core.regs 12 * s.core.regs 11) ∧ (run Q s detTape 13).core.regs 49 = (s.core.regs 11 + s.core.regs 11) ∧ (run Q s detTape 13).core.regs 50 = (0 : ℝ) ∧ (run Q s detTape 13).core.regs 53 = (2 : ℝ) ∧ (∀ x, x ≠ 40 → x ≠ 41 → x ≠ 47 → x ≠ 49 → x ≠ 50 → x ≠ 53 → (run Q s detTape 13).core.regs x = s.core.regs x) ∧ (run Q s detTape 13).core.mem = s.core.mem ∧ (run Q s detTape 13).integerMemory = s.integerMemory ∧ (run Q s detTape 13).work = s.work + 13 ∧ cellsWritten Q s 13 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (x : ℝ) (s : State) (hpc : s.core.pc = off + 13) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 17 + s.core.ptrs 46) = x) (hb0 : s.core.ptrs 46 < s.core.ptrs 60) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 7).core.pc = off + 13 ∧ (run Q s detTape 7).halted = false ∧ (run Q s detTape 7).core.ptrs 46 = s.core.ptrs 46 + 1 ∧ (run Q s detTape 7).core.ptrs 50 = s.core.ptrs 43 + s.core.ptrs 46 ∧ (∀ x, x ≠ 46 → x ≠ 50 → (run Q s detTape 7).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 7).core.regs 55 = x ∧ (∀ x, x ≠ 55 → (run Q s detTape 7).core.regs x = s.core.regs x) ∧ (run Q s detTape 7).core.mem (s.core.ptrs 43 + s.core.ptrs 46) = x ∧ (∀ z, z ≠ s.core.ptrs 43 + s.core.ptrs 46 → (run Q s detTape 7).core.mem z = s.core.mem z) ∧ (run Q s detTape 7).integerMemory = s.integerMemory ∧ (run Q s detTape 7).work = s.work + 7 ∧ ∀ c ∈ cellsWritten Q s 7, c = (true, s.core.ptrs 43 + s.core.ptrs 46)) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 13) (hh : s.halted = false) (hb0 : s.core.ptrs 60 ≤ s.core.ptrs 46) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 1).core.pc = off + 20 ∧ (run Q s detTape 1).halted = false ∧ (run Q s detTape 1).core.ptrs = s.core.ptrs ∧ (run Q s detTape 1).core.regs = s.core.regs ∧ (run Q s detTape 1).core.mem = s.core.mem ∧ (run Q s detTape 1).integerMemory = s.integerMemory ∧ (run Q s detTape 1).work = s.work + 1 ∧ cellsWritten Q s 1 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 20) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 14).core.pc = off + 34 ∧ (run Q s detTape 14).halted = false ∧ (run Q s detTape 14).core.ptrs 13 = s.core.ptrs 13 - 4 ∧ (run Q s detTape 14).core.ptrs 42 = s.core.ptrs 13 - 4 ∧ (run Q s detTape 14).core.ptrs 44 = s.core.ptrs 13 - 1 ∧ (run Q s detTape 14).core.ptrs 57 = s.core.ptrs 13 - 2 ∧ (run Q s detTape 14).core.ptrs 59 = s.core.ptrs 13 - 1 ∧ (∀ x, x ≠ 13 → x ≠ 42 → x ≠ 44 → x ≠ 57 → x ≠ 59 → (run Q s detTape 14).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 14).core.regs = s.core.regs ∧ (run Q s detTape 14).core.mem = s.core.mem ∧ (run Q s detTape 14).integerMemory (s.core.ptrs 13 - 4) = s.core.ptrs 43 ∧ (run Q s detTape 14).integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 13 - 1 ∧ (run Q s detTape 14).integerMemory (s.core.ptrs 13 - 2) = s.core.ptrs 40 ∧ (∀ z, z ≠ s.core.ptrs 13 - 4 → z ≠ s.core.ptrs 13 - 3 → z ≠ s.core.ptrs 13 - 2 → (run Q s detTape 14).integerMemory z = s.integerMemory z) ∧ (run Q s detTape 14).work = s.work + 14 ∧ ∀ c ∈ cellsWritten Q s 14, c = (false, s.core.ptrs 13 - 4) ∨ c = (false, s.core.ptrs 13 - 3) ∨ c = (false, s.core.ptrs 13 - 2)) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 34) (hh : s.halted = false) (hb0 : s.core.ptrs 40 ≤ s.core.ptrs 42) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 1).core.pc = off + 395 ∧ (run Q s detTape 1).halted = false ∧ (run Q s detTape 1).core.ptrs = s.core.ptrs ∧ (run Q s detTape 1).core.regs = s.core.regs ∧ (run Q s detTape 1).core.mem = s.core.mem ∧ (run Q s detTape 1).integerMemory = s.integerMemory ∧ (run Q s detTape 1).work = s.work + 1 ∧ cellsWritten Q s 1 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (rt : ℤ) (s : State) (hpc : s.core.pc = off + 395) (hh : s.halted = false) (fi0 : s.integerMemory (s.core.ptrs 59) = rt) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 1).core.pc = off + 396 ∧ (run Q s detTape 1).halted = false ∧ (run Q s detTape 1).core.ptrs 17 = rt ∧ (∀ x, x ≠ 17 → (run Q s detTape 1).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 1).core.regs = s.core.regs ∧ (run Q s detTape 1).core.mem = s.core.mem ∧ (run Q s detTape 1).integerMemory = s.integerMemory ∧ (run Q s detTape 1).work = s.work + 1 ∧ cellsWritten Q s 1 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (ep esl elink : ℤ) (s : State) (hpc : s.core.pc = off + 34) (hh : s.halted = false) (fi0 : s.integerMemory (s.core.ptrs 42) = ep) (fi1 : s.integerMemory (s.core.ptrs 42 + 1) = esl) (fi2 : s.integerMemory (s.core.ptrs 42 + 2) = elink) (hb0 : s.core.ptrs 42 < s.core.ptrs 40) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 11).core.pc = off + 45 ∧ (run Q s detTape 11).halted = false ∧ (run Q s detTape 11).core.ptrs 14 = s.core.ptrs 14 - s.core.ptrs 60 ∧ (run Q s detTape 11).core.ptrs 42 = elink ∧ (run Q s detTape 11).core.ptrs 43 = ep ∧ (run Q s detTape 11).core.ptrs 44 = esl ∧ (run Q s detTape 11).core.ptrs 45 = 0 ∧ (run Q s detTape 11).core.ptrs 48 = s.core.ptrs 14 - s.core.ptrs 60 ∧ (run Q s detTape 11).core.ptrs 49 = 0 ∧ (run Q s detTape 11).core.ptrs 57 = s.core.ptrs 42 + 2 ∧ (∀ x, x ≠ 14 → x ≠ 42 → x ≠ 43 → x ≠ 44 → x ≠ 45 → x ≠ 48 → x ≠ 49 → x ≠ 57 → (run Q s detTape 11).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 11).core.regs = s.core.regs ∧ (run Q s detTape 11).core.mem = s.core.mem ∧ (run Q s detTape 11).integerMemory = s.integerMemory ∧ (run Q s detTape 11).work = s.work + 11 ∧ cellsWritten Q s 11 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 45) (hh : s.halted = false) (hb0 : s.core.ptrs 11 ≤ s.core.ptrs 45) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 1).core.pc = off + 131 ∧ (run Q s detTape 1).halted = false ∧ (run Q s detTape 1).core.ptrs = s.core.ptrs ∧ (run Q s detTape 1).core.regs = s.core.regs ∧ (run Q s detTape 1).core.mem = s.core.mem ∧ (run Q s detTape 1).integerMemory = s.integerMemory ∧ (run Q s detTape 1).work = s.work + 1 ∧ cellsWritten Q s 1 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (ki pa : ℤ) (s : State) (hpc : s.core.pc = off + 45) (hh : s.halted = false) (fi0 : s.integerMemory (s.core.ptrs 10 + s.core.ptrs 45) = ki) (fi1 : s.integerMemory (s.core.ptrs 12 + ki) = pa) (hb0 : s.core.ptrs 45 < s.core.ptrs 11) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 8).core.pc = off + 53 ∧ (run Q s detTape 8).halted = false ∧ (run Q s detTape 8).core.ptrs 46 = 0 ∧ (run Q s detTape 8).core.ptrs 47 = pa ∧ (run Q s detTape 8).core.ptrs 57 = s.core.ptrs 12 + ki ∧ (∀ x, x ≠ 46 → x ≠ 47 → x ≠ 57 → (run Q s detTape 8).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 8).core.regs 42 = (0 : ℝ) ∧ (run Q s detTape 8).core.regs 43 = (0 : ℝ) ∧ (∀ x, x ≠ 42 → x ≠ 43 → (run Q s detTape 8).core.regs x = s.core.regs x) ∧ (run Q s detTape 8).core.mem = s.core.mem ∧ (run Q s detTape 8).integerMemory = s.integerMemory ∧ (run Q s detTape 8).work = s.work + 8 ∧ cellsWritten Q s 8 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 53) (hh : s.halted = false) (hb0 : s.core.ptrs 1 ≤ s.core.ptrs 46) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 1).core.pc = off + 86 ∧ (run Q s detTape 1).halted = false ∧ (run Q s detTape 1).core.ptrs = s.core.ptrs ∧ (run Q s detTape 1).core.regs = s.core.regs ∧ (run Q s detTape 1).core.mem = s.core.mem ∧ (run Q s detTape 1).integerMemory = s.integerMemory ∧ (run Q s detTape 1).work = s.work + 1 ∧ cellsWritten Q s 1 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (x lo hi : ℝ) (s : State) (hpc : s.core.pc = off + 53) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 47 + s.core.ptrs 46) = x) (fr1 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 46) = lo) (fr2 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 46 + s.core.ptrs 1) = hi) (hb0 : s.core.ptrs 46 < s.core.ptrs 1) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 33).core.pc = off + 53 ∧ (run Q s detTape 33).halted = false ∧ (run Q s detTape 33).core.ptrs 46 = s.core.ptrs 46 + 1 ∧ (run Q s detTape 33).core.ptrs 57 = s.core.ptrs 43 + s.core.ptrs 46 + s.core.ptrs 1 ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape 33).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 33).core.regs 42 = (s.core.regs 42 + (((((lo - x) + (((x - hi) + Real.sqrt ((x - hi) * (x - hi))) / s.core.regs 53)) + Real.sqrt (((lo - x) - (((x - hi) + Real.sqrt ((x - hi) * (x - hi))) / s.core.regs 53)) * ((lo - x) - (((x - hi) + Real.sqrt ((x - hi) * (x - hi))) / s.core.regs 53)))) / s.core.regs 53) * ((((lo - x) + (((x - hi) + Real.sqrt ((x - hi) * (x - hi))) / s.core.regs 53)) + Real.sqrt (((lo - x) - (((x - hi) + Real.sqrt ((x - hi) * (x - hi))) / s.core.regs 53)) * ((lo - x) - (((x - hi) + Real.sqrt ((x - hi) * (x - hi))) / s.core.regs 53)))) / s.core.regs 53))) ∧ (run Q s detTape 33).core.regs 43 = (s.core.regs 43 + (((((x - lo) + (hi - x)) + Real.sqrt (((x - lo) - (hi - x)) * ((x - lo) - (hi - x)))) / s.core.regs 53) * ((((x - lo) + (hi - x)) + Real.sqrt (((x - lo) - (hi - x)) * ((x - lo) - (hi - x)))) / s.core.regs 53))) ∧ (run Q s detTape 33).core.regs 44 = x ∧ (run Q s detTape 33).core.regs 45 = lo ∧ (run Q s detTape 33).core.regs 46 = hi ∧ (run Q s detTape 33).core.regs 47 = ((((x - lo) + (hi - x)) + Real.sqrt (((x - lo) - (hi - x)) * ((x - lo) - (hi - x)))) / s.core.regs 53) ∧ (run Q s detTape 33).core.regs 48 = (hi - x) ∧ (run Q s detTape 33).core.regs 54 = (((((x - lo) + (hi - x)) + Real.sqrt (((x - lo) - (hi - x)) * ((x - lo) - (hi - x)))) / s.core.regs 53) * ((((x - lo) + (hi - x)) + Real.sqrt (((x - lo) - (hi - x)) * ((x - lo) - (hi - x)))) / s.core.regs 53)) ∧ (∀ x, x ≠ 42 → x ≠ 43 → x ≠ 44 → x ≠ 45 → x ≠ 46 → x ≠ 47 → x ≠ 48 → x ≠ 54 → (run Q s detTape 33).core.regs x = s.core.regs x) ∧ (run Q s detTape 33).core.mem = s.core.mem ∧ (run Q s detTape 33).integerMemory = s.integerMemory ∧ (run Q s detTape 33).work = s.work + 33 ∧ cellsWritten Q s 33 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 86) (hh : s.halted = false) (hb0 : ¬ (s.core.regs 42 - s.core.regs 40) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 3).core.pc = off + 126 ∧ (run Q s detTape 3).halted = false ∧ (run Q s detTape 3).core.ptrs = s.core.ptrs ∧ (run Q s detTape 3).core.regs 54 = (s.core.regs 42 - s.core.regs 40) ∧ (∀ x, x ≠ 54 → (run Q s detTape 3).core.regs x = s.core.regs x) ∧ (run Q s detTape 3).core.mem = s.core.mem ∧ (run Q s detTape 3).integerMemory = s.integerMemory ∧ (run Q s detTape 3).work = s.work + 3 ∧ cellsWritten Q s 3 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 86) (hh : s.halted = false) (hb0 : (s.core.regs 42 - s.core.regs 40) ≤ 0) (hb1 : (s.core.regs 43 - s.core.regs 41) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 4).core.pc = off + 128 ∧ (run Q s detTape 4).halted = false ∧ (run Q s detTape 4).core.ptrs = s.core.ptrs ∧ (run Q s detTape 4).core.regs 54 = (s.core.regs 43 - s.core.regs 41) ∧ (∀ x, x ≠ 54 → (run Q s detTape 4).core.regs x = s.core.regs x) ∧ (run Q s detTape 4).core.mem = s.core.mem ∧ (run Q s detTape 4).integerMemory = s.integerMemory ∧ (run Q s detTape 4).work = s.work + 4 ∧ cellsWritten Q s 4 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 86) (hh : s.halted = false) (hb0 : (s.core.regs 42 - s.core.regs 40) ≤ 0) (hb1 : ¬ (s.core.regs 43 - s.core.regs 41) ≤ 0) (hb2 : s.core.ptrs 69 < s.core.ptrs 49) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 6).core.pc = off + 93 ∧ (run Q s detTape 6).halted = false ∧ (run Q s detTape 6).core.ptrs 46 = 0 ∧ (∀ x, x ≠ 46 → (run Q s detTape 6).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 6).core.regs 54 = (s.core.regs 43 - s.core.regs 41) ∧ (∀ x, x ≠ 54 → (run Q s detTape 6).core.regs x = s.core.regs x) ∧ (run Q s detTape 6).core.mem = s.core.mem ∧ (run Q s detTape 6).integerMemory = s.integerMemory ∧ (run Q s detTape 6).work = s.work + 6 ∧ cellsWritten Q s 6 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 86) (hh : s.halted = false) (hb0 : (s.core.regs 42 - s.core.regs 40) ≤ 0) (hb1 : ¬ (s.core.regs 43 - s.core.regs 41) ≤ 0) (hb2 : s.core.ptrs 49 ≤ s.core.ptrs 69) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 6).core.pc = off + 116 ∧ (run Q s detTape 6).halted = false ∧ (run Q s detTape 6).core.ptrs 46 = 0 ∧ (∀ x, x ≠ 46 → (run Q s detTape 6).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 6).core.regs 54 = (s.core.regs 43 - s.core.regs 41) ∧ (∀ x, x ≠ 54 → (run Q s detTape 6).core.regs x = s.core.regs x) ∧ (run Q s detTape 6).core.mem = s.core.mem ∧ (run Q s detTape 6).integerMemory = s.integerMemory ∧ (run Q s detTape 6).work = s.work + 6 ∧ cellsWritten Q s 6 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 93) (hh : s.halted = false) (hb0 : s.core.ptrs 1 ≤ s.core.ptrs 46) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 1).core.pc = off + 126 ∧ (run Q s detTape 1).halted = false ∧ (run Q s detTape 1).core.ptrs = s.core.ptrs ∧ (run Q s detTape 1).core.regs = s.core.regs ∧ (run Q s detTape 1).core.mem = s.core.mem ∧ (run Q s detTape 1).integerMemory = s.integerMemory ∧ (run Q s detTape 1).work = s.work + 1 ∧ cellsWritten Q s 1 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (x mn mx : ℝ) (s : State) (hpc : s.core.pc = off + 93) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 47 + s.core.ptrs 46) = x) (fr1 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 46) = mn) (fr2 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1) = mx) (hb0 : s.core.ptrs 46 < s.core.ptrs 1) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 23).core.pc = off + 93 ∧ (run Q s detTape 23).halted = false ∧ (run Q s detTape 23).core.ptrs 46 = s.core.ptrs 46 + 1 ∧ (run Q s detTape 23).core.ptrs 57 = s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1 ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape 23).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 23).core.regs 44 = x ∧ (run Q s detTape 23).core.regs 45 = mx ∧ (run Q s detTape 23).core.regs 47 = (((mx + x) + Real.sqrt ((mx - x) * (mx - x))) / s.core.regs 53) ∧ (run Q s detTape 23).core.regs 54 = Real.sqrt ((mx - x) * (mx - x)) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 47 → x ≠ 54 → (run Q s detTape 23).core.regs x = s.core.regs x) ∧ (run Q s detTape 23).core.mem (s.core.ptrs 48 + s.core.ptrs 46) = (((mn + x) - Real.sqrt ((mn - x) * (mn - x))) / s.core.regs 53) ∧ (run Q s detTape 23).core.mem (s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1) = (((mx + x) + Real.sqrt ((mx - x) * (mx - x))) / s.core.regs 53) ∧ (∀ z, z ≠ s.core.ptrs 48 + s.core.ptrs 46 → z ≠ s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1 → (run Q s detTape 23).core.mem z = s.core.mem z) ∧ (run Q s detTape 23).integerMemory = s.integerMemory ∧ (run Q s detTape 23).work = s.work + 23 ∧ ∀ c ∈ cellsWritten Q s 23, c = (true, s.core.ptrs 48 + s.core.ptrs 46) ∨ c = (true, s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1)) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (x : ℝ) (s : State) (hpc : s.core.pc = off + 116) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 47 + s.core.ptrs 46) = x) (hb0 : s.core.ptrs 46 < s.core.ptrs 1) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 9).core.pc = off + 116 ∧ (run Q s detTape 9).halted = false ∧ (run Q s detTape 9).core.ptrs 46 = s.core.ptrs 46 + 1 ∧ (run Q s detTape 9).core.ptrs 57 = s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1 ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape 9).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 9).core.regs 44 = x ∧ (∀ x, x ≠ 44 → (run Q s detTape 9).core.regs x = s.core.regs x) ∧ (run Q s detTape 9).core.mem (s.core.ptrs 48 + s.core.ptrs 46) = x ∧ (run Q s detTape 9).core.mem (s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1) = x ∧ (∀ z, z ≠ s.core.ptrs 48 + s.core.ptrs 46 → z ≠ s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1 → (run Q s detTape 9).core.mem z = s.core.mem z) ∧ (run Q s detTape 9).integerMemory = s.integerMemory ∧ (run Q s detTape 9).work = s.work + 9 ∧ ∀ c ∈ cellsWritten Q s 9, c = (true, s.core.ptrs 48 + s.core.ptrs 46) ∨ c = (true, s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1)) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 116) (hh : s.halted = false) (hb0 : s.core.ptrs 1 ≤ s.core.ptrs 46) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 2).core.pc = off + 126 ∧ (run Q s detTape 2).halted = false ∧ (run Q s detTape 2).core.ptrs 49 = 1 ∧ (∀ x, x ≠ 49 → (run Q s detTape 2).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 2).core.regs = s.core.regs ∧ (run Q s detTape 2).core.mem = s.core.mem ∧ (run Q s detTape 2).integerMemory = s.integerMemory ∧ (run Q s detTape 2).work = s.work + 2 ∧ cellsWritten Q s 2 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 126) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 2).core.pc = off + 45 ∧ (run Q s detTape 2).halted = false ∧ (run Q s detTape 2).core.ptrs 45 = s.core.ptrs 45 + 1 ∧ (∀ x, x ≠ 45 → (run Q s detTape 2).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 2).core.regs = s.core.regs ∧ (run Q s detTape 2).core.mem = s.core.mem ∧ (run Q s detTape 2).integerMemory = s.integerMemory ∧ (run Q s detTape 2).work = s.work + 2 ∧ cellsWritten Q s 2 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 128) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 3).core.pc = off + 383 ∧ (run Q s detTape 3).halted = false ∧ (run Q s detTape 3).core.ptrs 61 = s.core.ptrs 45 + 1 ∧ (∀ x, x ≠ 61 → (run Q s detTape 3).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 3).core.regs = s.core.regs ∧ (run Q s detTape 3).core.mem = s.core.mem ∧ (run Q s detTape 3).integerMemory = s.integerMemory ∧ (run Q s detTape 3).work = s.work + 3 ∧ cellsWritten Q s 3 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 131) (hh : s.halted = false) (hb0 : s.core.ptrs 49 ≤ s.core.ptrs 69) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 2).core.pc = off + 383 ∧ (run Q s detTape 2).halted = false ∧ (run Q s detTape 2).core.ptrs 61 = 0 ∧ (∀ x, x ≠ 61 → (run Q s detTape 2).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 2).core.regs = s.core.regs ∧ (run Q s detTape 2).core.mem = s.core.mem ∧ (run Q s detTape 2).integerMemory = s.integerMemory ∧ (run Q s detTape 2).work = s.work + 2 ∧ cellsWritten Q s 2 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 131) (hh : s.halted = false) (hb0 : s.core.ptrs 69 < s.core.ptrs 49) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 3).core.pc = off + 134 ∧ (run Q s detTape 3).halted = false ∧ (run Q s detTape 3).core.ptrs 46 = 0 ∧ (run Q s detTape 3).core.ptrs 61 = 0 ∧ (∀ x, x ≠ 46 → x ≠ 61 → (run Q s detTape 3).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 3).core.regs = s.core.regs ∧ (run Q s detTape 3).core.mem = s.core.mem ∧ (run Q s detTape 3).integerMemory = s.integerMemory ∧ (run Q s detTape 3).work = s.work + 3 ∧ cellsWritten Q s 3 = ∅) := by sorry
end DetANN.HPIM.BDSource
Original, written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions' as part of a floor-free proof of DetANN.lemma_3_3 (Feng, Indyk, STOC 2027 submission, Lemma 3.3, p.7). These are pieces of the BSP construction block of DetANN.HPIM.build_block, split out so that each proof fits the verifier's time limit. The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure.