Distance-oracle construction of an exact threshold-graph arc array
ProvedStableMSR.Recovery.Compiler.ThresholdGraph.threshold_graph_array_programOne fixed deterministic program with instructions constructs the directed arc array of a distance-threshold graph by querying the distance oracle. For indexed points, any real threshold , and any integer output base , the program examines every ordered pair, omits self-pairs, and writes exactly the arcs
No metric or symmetry hypothesis is required for this array construction; when is symmetric it is a sound complete directed representation of the ordinary simple threshold graph.
Given only , and in designated registers, with otherwise arbitrary initial registers and memory, one actual interpreter run halts after exactly
charged steps and makes exactly distance queries. It returns a list of at most arcs encoded as consecutive zero-based endpoint pairs at , the exact arc count in a register, and the endpoint cursor
Every pair occurs in the list if and only if it satisfies the displayed condition. All integer memory outside , all real memory, random-tape position, non-work pointer registers and real registers other than two query scratch registers are preserved. Output cells may initially contain arbitrary data. The threshold register survives. The empty input executes no oracle query and halts in eight steps. Negative thresholds, threshold ties and negative output addresses are included.
This supplies executable graph-array construction for subsequent connected-component, external-boundary and state-table programs, and can be placed after a generated catalog because it preserves all earlier memory. It is a supporting threshold-graph primitive. Selection of the paper's net/region vertex set, the complete canonical catalog/graph/state-table composition, recurrence evaluation, geometry and full clustering recovery are separate obligations.
import Definitions.Def_StableMSR_ComponentGraphMemory open scoped Classical open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.ComponentMemory
theorem StableMSR.Recovery.Compiler.ThresholdGraph.threshold_graph_array_program :
∃ P : MinSumFPT.Program, DeterministicProgram P ∧ P.length = 47 ∧
∀ (n : ℕ) (d : Point n → Point n → ℝ) (R : ℝ) (b : ℤ) (s : Store),
s.ptrs 6 = (n:ℤ) → s.ptrs 84 = b → s.regs 89 = R →
∀ (ω : ℕ → ℝ) (work : ℕ),
∃ es : List (Fin n × Fin n), es.length ≤ n^2 ∧
let result := (MinSumFPT.step P d ω)^[n*(14*n+6)+8] (s.state 0 work)
result.halted = true ∧ result.work = work+(n*(14*n+6)+8) ∧
result.cfg.ptrs 85 = (es.length:ℤ) ∧ result.cfg.ptrs 83 = b+2*(es.length:ℤ) ∧
EdgeEncoding result.imem b es ∧
(∀ u v : Fin n, (u,v) ∈ es ↔ u ≠ v ∧ d u v ≤ R) ∧
(∀ x : ℤ, (x < b ∨ b+2*(n:ℤ)^2 ≤ x) → result.imem x = s.imem x) ∧
(∀ j : ℕ, j ∉ ([80,81,82,83,85]:List ℕ) → result.cfg.ptrs j = s.ptrs j) ∧
(∀ j : ℕ, j ≠ 90 → j ≠ 91 → result.cfg.regs j = s.regs j) ∧
result.cfg.mem = s.mem ∧ result.queries = s.queries+n^2 ∧ result.tapePos = s.tapePos := by sorry