Algorithm 1 initialization: an exact-k partition in 5n+12 interpreter steps
ProvedStableMSR.Recovery.feasible_fallback_programThere is one finite deterministic program , independent of all input data, that initializes a feasible clustering on every input with . At exactly
steps of the canonical interpreter, its state has halted, has charged exactly units of work, and contains validated surjective labels whose decoded fibers form a feasible partition into exactly nonempty clusters. The distance array can be arbitrary: metricity and stability are not required.
This implements the feasible-answer initialization in Algorithm 1. It includes , , and . It supplies initialization only and does not assert recovery of the optimum for general .
Formalization Note. The program is selected before , and the result concerns actual execute states and charged work in the existing machine model.
import Definitions.Def_StableMSR_Recovery_Execution set_option autoImplicit false open scoped Classical
namespace StableMSR.Recovery
theorem feasible_fallback_program :
∃ P : MinSumFPT.Program, DeterministicProgram P ∧
∀ (n k : ℕ) (d : Point n → Point n → ℝ), 1 ≤ k → k ≤ n →
let s := execute P n k d (5*n+12)
s.halted = true ∧ s.work = 5*n+12 ∧ ValidLabels n k s ∧
Feasible Finset.univ k (outputPartition n k s) := by sorry
end StableMSR.Recovery