Straight-line segments of the BSP construction block: core box, sides, split and copy
ProvedDetANN.HPIM.BD.split_stepsapproximate-nearest-neighborcomputational-geometrydata-structures
Twenty-one straight-line facts about the program of definition DetANN_HPIMBuildProg: the core box, the longest sides, the split and the copy-and-set subroutine.
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 .
- Core exit (1): when .
- Core step (27): coordinate of becomes , where is the task box at pointer 43.
- Sides start (11): reals 51, 52 := the side 0 of and of the task box; .
- Sides exit (1).
- Sides step (25): reals 51, 52 take the maximum with side .
- Carve (3): when .
- Split (4): otherwise; axis .
- Axis, next (9): when side : .
- Axis, found (7): when side : reals .
- Split node (16): real ; a cut node at with ; copy-and-set of the task box with index and code 0.
- Left push (17): pushes ; copy-and-set of the task box with index and code 1.
- Right push (15): pushes .
- Copy head (3): pointers , .
- Copy step (7): when , real cell gets the value of .
- Copy exit (1). 16–21. Set and return, codes 0–5 (3, 5, 7, 9, 11, 12 steps): real cell gets real 44, then the return by the code in pointer 58.
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 split_steps :
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 134) (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 + 161 ∧ (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) (mn lo mx hi : ℝ) (s : State) (hpc : s.core.pc = off + 134) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 46) = mn) (fr1 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 46) = lo) (fr2 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1) = mx) (fr3 : 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) (hx0 : s.core.ptrs 48 < s.core.ptrs 43),
(run Q s detTape 27).core.pc = off + 134 ∧ (run Q s detTape 27).halted = false ∧ (run Q s detTape 27).core.ptrs 46 = s.core.ptrs 46 + 1 ∧ (run Q s detTape 27).core.ptrs 50 = s.core.ptrs 43 + s.core.ptrs 46 + s.core.ptrs 1 ∧ (run Q s detTape 27).core.ptrs 57 = s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1 ∧ (∀ x, x ≠ 46 → x ≠ 50 → x ≠ 57 → (run Q s detTape 27).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 27).core.regs 44 = (mx + s.core.regs 49) ∧ (run Q s detTape 27).core.regs 45 = hi ∧ (run Q s detTape 27).core.regs 47 = ((((mx + s.core.regs 49) + hi) - Real.sqrt (((mx + s.core.regs 49) - hi) * ((mx + s.core.regs 49) - hi))) / s.core.regs 53) ∧ (run Q s detTape 27).core.regs 54 = Real.sqrt (((mx + s.core.regs 49) - hi) * ((mx + s.core.regs 49) - hi)) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 47 → x ≠ 54 → (run Q s detTape 27).core.regs x = s.core.regs x) ∧ (run Q s detTape 27).core.mem (s.core.ptrs 48 + s.core.ptrs 46) = ((((mn - s.core.regs 49) + lo) + Real.sqrt (((mn - s.core.regs 49) - lo) * ((mn - s.core.regs 49) - lo))) / s.core.regs 53) ∧ (run Q s detTape 27).core.mem (s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1) = ((((mx + s.core.regs 49) + hi) - Real.sqrt (((mx + s.core.regs 49) - hi) * ((mx + s.core.regs 49) - hi))) / 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 27).core.mem z = s.core.mem z) ∧ (run Q s detTape 27).integerMemory = s.integerMemory ∧ (run Q s detTape 27).work = s.work + 27 ∧ ∀ c ∈ cellsWritten Q s 27, 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) (a0 b0 c0 d0 : ℝ) (s : State) (hpc : s.core.pc = off + 161) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 48) = a0) (fr1 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 1) = b0) (fr2 : s.core.mem (s.core.ptrs 43) = c0) (fr3 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 1) = d0) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 11).core.pc = off + 172 ∧ (run Q s detTape 11).halted = false ∧ (run Q s detTape 11).core.ptrs 46 = 1 ∧ (run Q s detTape 11).core.ptrs 57 = s.core.ptrs 43 + s.core.ptrs 1 ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape 11).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 11).core.regs 44 = c0 ∧ (run Q s detTape 11).core.regs 45 = d0 ∧ (run Q s detTape 11).core.regs 51 = (b0 - a0) ∧ (run Q s detTape 11).core.regs 52 = (d0 - c0) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 51 → x ≠ 52 → (run Q s detTape 11).core.regs x = s.core.regs x) ∧ (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 + 172) (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 + 197 ∧ (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) (a b c d : ℝ) (s : State) (hpc : s.core.pc = off + 172) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 46) = a) (fr1 : s.core.mem (s.core.ptrs 48 + s.core.ptrs 46 + s.core.ptrs 1) = b) (fr2 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 46) = c) (fr3 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 46 + s.core.ptrs 1) = d) (hb0 : s.core.ptrs 46 < s.core.ptrs 1) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 25).core.pc = off + 172 ∧ (run Q s detTape 25).halted = false ∧ (run Q s detTape 25).core.ptrs 46 = s.core.ptrs 46 + 1 ∧ (run Q s detTape 25).core.ptrs 57 = s.core.ptrs 43 + s.core.ptrs 46 + s.core.ptrs 1 ∧ (∀ x, x ≠ 46 → x ≠ 57 → (run Q s detTape 25).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 25).core.regs 44 = c ∧ (run Q s detTape 25).core.regs 45 = d ∧ (run Q s detTape 25).core.regs 47 = (d - c) ∧ (run Q s detTape 25).core.regs 51 = (((s.core.regs 51 + (b - a)) + Real.sqrt ((s.core.regs 51 - (b - a)) * (s.core.regs 51 - (b - a)))) / s.core.regs 53) ∧ (run Q s detTape 25).core.regs 52 = (((s.core.regs 52 + (d - c)) + Real.sqrt ((s.core.regs 52 - (d - c)) * (s.core.regs 52 - (d - c)))) / s.core.regs 53) ∧ (run Q s detTape 25).core.regs 54 = Real.sqrt ((s.core.regs 52 - (d - c)) * (s.core.regs 52 - (d - c))) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 47 → x ≠ 51 → x ≠ 52 → x ≠ 54 → (run Q s detTape 25).core.regs x = s.core.regs x) ∧ (run Q s detTape 25).core.mem = s.core.mem ∧ (run Q s detTape 25).integerMemory = s.integerMemory ∧ (run Q s detTape 25).work = s.work + 25 ∧ cellsWritten Q s 25 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 197) (hh : s.halted = false) (hb0 : ((s.core.regs 51 + s.core.regs 51) - s.core.regs 52) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 3).core.pc = off + 280 ∧ (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 51 + s.core.regs 51) - s.core.regs 52) ∧ (∀ 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 + 197) (hh : s.halted = false) (hb0 : ¬ ((s.core.regs 51 + s.core.regs 51) - s.core.regs 52) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 4).core.pc = off + 201 ∧ (run Q s detTape 4).halted = false ∧ (run Q s detTape 4).core.ptrs 53 = 0 ∧ (∀ x, x ≠ 53 → (run Q s detTape 4).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 4).core.regs 54 = ((s.core.regs 51 + s.core.regs 51) - s.core.regs 52) ∧ (∀ 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) (a b : ℝ) (s : State) (hpc : s.core.pc = off + 201) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 53) = a) (fr1 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 53 + s.core.ptrs 1) = b) (hb0 : ¬ (s.core.regs 52 - (b - a)) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 9).core.pc = off + 201 ∧ (run Q s detTape 9).halted = false ∧ (run Q s detTape 9).core.ptrs 53 = s.core.ptrs 53 + 1 ∧ (run Q s detTape 9).core.ptrs 57 = s.core.ptrs 43 + s.core.ptrs 53 + s.core.ptrs 1 ∧ (∀ x, x ≠ 53 → x ≠ 57 → (run Q s detTape 9).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 9).core.regs 44 = a ∧ (run Q s detTape 9).core.regs 45 = b ∧ (run Q s detTape 9).core.regs 47 = (b - a) ∧ (run Q s detTape 9).core.regs 54 = (s.core.regs 52 - (b - a)) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 47 → x ≠ 54 → (run Q s detTape 9).core.regs x = s.core.regs x) ∧ (run Q s detTape 9).core.mem = s.core.mem ∧ (run Q s detTape 9).integerMemory = s.integerMemory ∧ (run Q s detTape 9).work = s.work + 9 ∧ cellsWritten Q s 9 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (a b : ℝ) (s : State) (hpc : s.core.pc = off + 201) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 53) = a) (fr1 : s.core.mem (s.core.ptrs 43 + s.core.ptrs 53 + s.core.ptrs 1) = b) (hb0 : (s.core.regs 52 - (b - a)) ≤ 0) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 7).core.pc = off + 210 ∧ (run Q s detTape 7).halted = false ∧ (run Q s detTape 7).core.ptrs 57 = s.core.ptrs 43 + s.core.ptrs 53 + s.core.ptrs 1 ∧ (∀ x, x ≠ 57 → (run Q s detTape 7).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 7).core.regs 44 = a ∧ (run Q s detTape 7).core.regs 45 = b ∧ (run Q s detTape 7).core.regs 47 = (b - a) ∧ (run Q s detTape 7).core.regs 54 = (s.core.regs 52 - (b - a)) ∧ (∀ x, x ≠ 44 → x ≠ 45 → x ≠ 47 → x ≠ 54 → (run Q s detTape 7).core.regs x = s.core.regs x) ∧ (run Q s detTape 7).core.mem = s.core.mem ∧ (run Q s detTape 7).integerMemory = s.integerMemory ∧ (run Q s detTape 7).work = s.work + 7 ∧ cellsWritten Q s 7 = ∅) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 210) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1) (hx0 : s.core.ptrs 13 ≤ s.core.ptrs 44),
(run Q s detTape 16).core.pc = off + 258 ∧ (run Q s detTape 16).halted = false ∧ (run Q s detTape 16).core.ptrs 13 = s.core.ptrs 13 - 4 ∧ (run Q s detTape 16).core.ptrs 50 = s.core.ptrs 43 ∧ (run Q s detTape 16).core.ptrs 51 = s.core.ptrs 1 + s.core.ptrs 53 ∧ (run Q s detTape 16).core.ptrs 52 = s.core.ptrs 13 - 4 ∧ (run Q s detTape 16).core.ptrs 57 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 16).core.ptrs 58 = 0 ∧ (∀ x, x ≠ 13 → x ≠ 50 → x ≠ 51 → x ≠ 52 → x ≠ 57 → x ≠ 58 → (run Q s detTape 16).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 16).core.regs 44 = ((s.core.regs 44 + s.core.regs 45) / s.core.regs 53) ∧ (∀ x, x ≠ 44 → (run Q s detTape 16).core.regs x = s.core.regs x) ∧ (run Q s detTape 16).core.mem = s.core.mem ∧ (run Q s detTape 16).integerMemory (s.core.ptrs 13 - 4) = s.core.ptrs 68 ∧ (run Q s detTape 16).integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 43 ∧ (run Q s detTape 16).integerMemory (s.core.ptrs 44) = s.core.ptrs 13 - 4 ∧ (∀ z, z ≠ s.core.ptrs 13 - 4 → z ≠ s.core.ptrs 13 - 3 → z ≠ s.core.ptrs 44 → (run Q s detTape 16).integerMemory z = s.integerMemory z) ∧ (run Q s detTape 16).work = s.work + 16 ∧ ∀ c ∈ cellsWritten Q s 16, c = (false, s.core.ptrs 13 - 4) ∨ c = (false, s.core.ptrs 13 - 3) ∨ c = (false, s.core.ptrs 44)) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 226) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 17).core.pc = off + 258 ∧ (run Q s detTape 17).halted = false ∧ (run Q s detTape 17).core.ptrs 13 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 17).core.ptrs 42 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 17).core.ptrs 50 = s.core.ptrs 43 ∧ (run Q s detTape 17).core.ptrs 51 = s.core.ptrs 53 ∧ (run Q s detTape 17).core.ptrs 57 = s.core.ptrs 13 - 1 ∧ (run Q s detTape 17).core.ptrs 58 = 1 ∧ (run Q s detTape 17).core.ptrs 62 = s.core.ptrs 52 + 2 ∧ (∀ x, x ≠ 13 → x ≠ 42 → x ≠ 50 → x ≠ 51 → x ≠ 57 → x ≠ 58 → x ≠ 62 → (run Q s detTape 17).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 17).core.regs = s.core.regs ∧ (run Q s detTape 17).core.mem = s.core.mem ∧ (run Q s detTape 17).integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 56 ∧ (run Q s detTape 17).integerMemory (s.core.ptrs 13 - 2) = s.core.ptrs 52 + 2 ∧ (run Q s detTape 17).integerMemory (s.core.ptrs 13 - 1) = s.core.ptrs 42 ∧ (∀ z, z ≠ s.core.ptrs 13 - 3 → z ≠ s.core.ptrs 13 - 2 → z ≠ s.core.ptrs 13 - 1 → (run Q s detTape 17).integerMemory z = s.integerMemory z) ∧ (run Q s detTape 17).work = s.work + 17 ∧ ∀ c ∈ cellsWritten Q s 17, c = (false, s.core.ptrs 13 - 3) ∨ c = (false, s.core.ptrs 13 - 2) ∨ c = (false, s.core.ptrs 13 - 1)) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 243) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 15).core.pc = off + 34 ∧ (run Q s detTape 15).halted = false ∧ (run Q s detTape 15).core.ptrs 13 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 15).core.ptrs 42 = s.core.ptrs 13 - 3 ∧ (run Q s detTape 15).core.ptrs 57 = s.core.ptrs 13 - 1 ∧ (run Q s detTape 15).core.ptrs 62 = s.core.ptrs 52 + 3 ∧ (∀ x, x ≠ 13 → x ≠ 42 → x ≠ 57 → x ≠ 62 → (run Q s detTape 15).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 15).core.regs = s.core.regs ∧ (run Q s detTape 15).core.mem = s.core.mem ∧ (run Q s detTape 15).integerMemory (s.core.ptrs 13 - 3) = s.core.ptrs 56 ∧ (run Q s detTape 15).integerMemory (s.core.ptrs 13 - 2) = s.core.ptrs 52 + 3 ∧ (run Q s detTape 15).integerMemory (s.core.ptrs 13 - 1) = s.core.ptrs 42 ∧ (∀ z, z ≠ s.core.ptrs 13 - 3 → z ≠ s.core.ptrs 13 - 2 → z ≠ s.core.ptrs 13 - 1 → (run Q s detTape 15).integerMemory z = s.integerMemory z) ∧ (run Q s detTape 15).work = s.work + 15 ∧ ∀ c ∈ cellsWritten Q s 15, c = (false, s.core.ptrs 13 - 3) ∨ c = (false, s.core.ptrs 13 - 2) ∨ c = (false, s.core.ptrs 13 - 1)) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 258) (hh : s.halted = false) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 3).core.pc = off + 261 ∧ (run Q s detTape 3).halted = false ∧ (run Q s detTape 3).core.ptrs 14 = s.core.ptrs 14 - s.core.ptrs 60 ∧ (run Q s detTape 3).core.ptrs 46 = 0 ∧ (run Q s detTape 3).core.ptrs 56 = s.core.ptrs 14 - s.core.ptrs 60 ∧ (∀ x, x ≠ 14 → x ≠ 46 → x ≠ 56 → (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) (x : ℝ) (s : State) (hpc : s.core.pc = off + 261) (hh : s.halted = false) (fr0 : s.core.mem (s.core.ptrs 50 + 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 + 261 ∧ (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 57 = s.core.ptrs 56 + s.core.ptrs 46 ∧ (∀ x, x ≠ 46 → x ≠ 57 → (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 56 + s.core.ptrs 46) = x ∧ (∀ z, z ≠ s.core.ptrs 56 + 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 56 + s.core.ptrs 46)) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 261) (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 + 268 ∧ (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 + 268) (hh : s.halted = false) (hb0 : s.core.ptrs 58 ≤ s.core.ptrs 69) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 3).core.pc = off + 226 ∧ (run Q s detTape 3).halted = false ∧ (run Q s detTape 3).core.ptrs 57 = s.core.ptrs 56 + s.core.ptrs 51 ∧ (∀ x, x ≠ 57 → (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.ptrs 56 + s.core.ptrs 51) = s.core.regs 44 ∧ (∀ z, z ≠ s.core.ptrs 56 + s.core.ptrs 51 → (run Q s detTape 3).core.mem z = s.core.mem z) ∧ (run Q s detTape 3).integerMemory = s.integerMemory ∧ (run Q s detTape 3).work = s.work + 3 ∧ ∀ c ∈ cellsWritten Q s 3, c = (true, s.core.ptrs 56 + s.core.ptrs 51)) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 268) (hh : s.halted = false) (hb0 : s.core.ptrs 69 < s.core.ptrs 58) (hb1 : s.core.ptrs 58 ≤ 1) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 5).core.pc = off + 243 ∧ (run Q s detTape 5).halted = false ∧ (run Q s detTape 5).core.ptrs 57 = 1 ∧ (∀ x, x ≠ 57 → (run Q s detTape 5).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 5).core.regs = s.core.regs ∧ (run Q s detTape 5).core.mem (s.core.ptrs 56 + s.core.ptrs 51) = s.core.regs 44 ∧ (∀ z, z ≠ s.core.ptrs 56 + s.core.ptrs 51 → (run Q s detTape 5).core.mem z = s.core.mem z) ∧ (run Q s detTape 5).integerMemory = s.integerMemory ∧ (run Q s detTape 5).work = s.work + 5 ∧ ∀ c ∈ cellsWritten Q s 5, c = (true, s.core.ptrs 56 + s.core.ptrs 51)) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 268) (hh : s.halted = false) (hb0 : s.core.ptrs 69 < s.core.ptrs 58) (hb1 : 1 < s.core.ptrs 58) (hb2 : s.core.ptrs 58 ≤ 2) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 7).core.pc = off + 304 ∧ (run Q s detTape 7).halted = false ∧ (run Q s detTape 7).core.ptrs 57 = 2 ∧ (∀ x, x ≠ 57 → (run Q s detTape 7).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 7).core.regs = s.core.regs ∧ (run Q s detTape 7).core.mem (s.core.ptrs 56 + s.core.ptrs 51) = s.core.regs 44 ∧ (∀ z, z ≠ s.core.ptrs 56 + s.core.ptrs 51 → (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 56 + s.core.ptrs 51)) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 268) (hh : s.halted = false) (hb0 : s.core.ptrs 69 < s.core.ptrs 58) (hb1 : 1 < s.core.ptrs 58) (hb2 : 2 < s.core.ptrs 58) (hb3 : s.core.ptrs 58 ≤ 3) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 9).core.pc = off + 321 ∧ (run Q s detTape 9).halted = false ∧ (run Q s detTape 9).core.ptrs 57 = 3 ∧ (∀ x, x ≠ 57 → (run Q s detTape 9).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 9).core.regs = s.core.regs ∧ (run Q s detTape 9).core.mem (s.core.ptrs 56 + s.core.ptrs 51) = s.core.regs 44 ∧ (∀ z, z ≠ s.core.ptrs 56 + s.core.ptrs 51 → (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 56 + s.core.ptrs 51)) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 268) (hh : s.halted = false) (hb0 : s.core.ptrs 69 < s.core.ptrs 58) (hb1 : 1 < s.core.ptrs 58) (hb2 : 2 < s.core.ptrs 58) (hb3 : 3 < s.core.ptrs 58) (hb4 : s.core.ptrs 58 ≤ 4) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 11).core.pc = off + 348 ∧ (run Q s detTape 11).halted = false ∧ (run Q s detTape 11).core.ptrs 57 = 4 ∧ (∀ x, 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.ptrs 56 + s.core.ptrs 51) = s.core.regs 44 ∧ (∀ z, z ≠ s.core.ptrs 56 + s.core.ptrs 51 → (run Q s detTape 11).core.mem z = s.core.mem z) ∧ (run Q s detTape 11).integerMemory = s.integerMemory ∧ (run Q s detTape 11).work = s.work + 11 ∧ ∀ c ∈ cellsWritten Q s 11, c = (true, s.core.ptrs 56 + s.core.ptrs 51)) ∧
(∀ (Q : Program) (off : ℕ) (hE : Embeds Q (bd off) off) (s : State) (hpc : s.core.pc = off + 268) (hh : s.halted = false) (hb0 : s.core.ptrs 69 < s.core.ptrs 58) (hb1 : 1 < s.core.ptrs 58) (hb2 : 2 < s.core.ptrs 58) (hb3 : 3 < s.core.ptrs 58) (hb4 : 4 < s.core.ptrs 58) (hm1 : 1 ≤ s.core.ptrs 1),
(run Q s detTape 12).core.pc = off + 366 ∧ (run Q s detTape 12).halted = false ∧ (run Q s detTape 12).core.ptrs 57 = 4 ∧ (∀ x, x ≠ 57 → (run Q s detTape 12).core.ptrs x = s.core.ptrs x) ∧ (run Q s detTape 12).core.regs = s.core.regs ∧ (run Q s detTape 12).core.mem (s.core.ptrs 56 + s.core.ptrs 51) = s.core.regs 44 ∧ (∀ z, z ≠ s.core.ptrs 56 + s.core.ptrs 51 → (run Q s detTape 12).core.mem z = s.core.mem z) ∧ (run Q s detTape 12).integerMemory = s.integerMemory ∧ (run Q s detTape 12).work = s.work + 12 ∧ ∀ c ∈ cellsWritten Q s 12, c = (true, s.core.ptrs 56 + s.core.ptrs 51)) := 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.