Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A fixed charged program for variable-width key-table lookup

Proved
StableMSR.Recovery.Compiler.TableLookup.table_lookup_program

by lreyzin · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmsformal-verification

One deterministic program with 464646 instructions searches an ordinary integer-memory table containing qqq consecutive records. Each record contains an LLL-cell integer key followed by one integer payload. The query is another LLL-cell array. The program initializes its result and scans the records in order, comparing every key against the query.

It halts after exactly

q(11L+16)+12q(11L+16)+12q(11L+16)+12

charged interpreter steps. If no key matches, the returned index is the sentinel qqq and the payload is 000. Otherwise it returns the greatest index of a matching record and that record's actual stored payload. In particular a uniquely matching key retrieves its record. Duplicate keys have defined behavior: the last matching record wins.

The result includes empty tables, zero-length keys, arbitrary integer entries, arbitrary initial output registers, and arbitrary initial work counters. For zero-length keys every record matches, so a nonempty table returns its last payload. All memory is read-only, and the query/table addresses, dimensions, real registers, oracle-query count, and tape position are preserved. The program and its finite instruction count are independent of qqq and LLL. The theorem supplies a concrete lookup primitive for state tables; construction and population of those tables remain separate obligations.

Preamble
import Definitions.Def_StableMSR_ComponentGraphMemory
import Mathlib.Combinatorics.SimpleGraph.Basic
open scoped Classical
open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.ComponentMemory
Formal statement
theorem StableMSR.Recovery.Compiler.TableLookup.table_lookup_program :
    ∃ P : MinSumFPT.Program, DeterministicProgram P ∧ P.length = 46 ∧
    ∀ (N q L : ℕ) (d : Point N → Point N → ℝ) (s : Store),
      s.ptrs 5 = (q : ℤ) → s.ptrs 6 = (L : ℤ) →
      ∀ (ω : ℕ → ℝ) (work : ℕ),
      let result := (MinSumFPT.step P d ω)^[q*(11*L+16)+12] (s.state 0 work)
      result.halted = true ∧ result.work = work+(q*(11*L+16)+12) ∧
      result.queries = s.queries ∧ result.tapePos = s.tapePos ∧
      result.cfg.mem = s.mem ∧ result.cfg.regs = s.regs ∧ result.imem = s.imem ∧
      (result.cfg.ptrs 25 = (q : ℤ) ↔
        ∀ i : Fin q, ¬ (∀ j : Fin L, s.imem (s.ptrs 3+(j.val : ℤ)) =
          s.imem (s.ptrs 2+(i.val : ℤ)*((L : ℤ)+1)+(j.val : ℤ)))) ∧
      (result.cfg.ptrs 25 = (q : ℤ) → result.cfg.ptrs 26 = 0) ∧
      (result.cfg.ptrs 25 ≠ (q : ℤ) →
        ∃ i : Fin q, result.cfg.ptrs 25 = (i.val : ℤ) ∧
          (∀ j : Fin L, s.imem (s.ptrs 3+(j.val : ℤ)) =
            s.imem (s.ptrs 2+(i.val : ℤ)*((L : ℤ)+1)+(j.val : ℤ))) ∧
          result.cfg.ptrs 26 = s.imem (s.ptrs 2+(i.val : ℤ)*((L : ℤ)+1)+(L : ℤ)) ∧
          ∀ k : Fin q, (∀ j : Fin L, s.imem (s.ptrs 3+(j.val : ℤ)) =
            s.imem (s.ptrs 2+(k.val : ℤ)*((L : ℤ)+1)+(j.val : ℤ))) →
              k.val ≤ i.val) ∧
      (0 ≤ result.cfg.ptrs 25 ∧ result.cfg.ptrs 25 ≤ (q : ℤ)) ∧
      (∀ j : ℕ, j ∉ ([0,4,18,20,21,22,23,24,25,26,27,28,29,30,32] : List ℕ) →
        result.cfg.ptrs j = s.ptrs j) := by sorry
Source
Exact Sum-of-Radii Clustering under Any Constant Stability; Prove2Me mission 11d3e3d6-df23-4c6a-8fd7-fbb629791a9b; executable comparisons and state-table lookup supporting rational_recovery_program.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me