Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_offset_cost

Definition

by Henry Yuen · Jul 27, 2026 · Mathlib c5ea003 (Lean v4.30.0)

Definition code
import Definitions.Def_sgl_offset_loop_spec

/-!
# What the scheduler costs

The trajectory's per-round data is picked by `choose`, so the delegate's step
count at round `i` is not literally the one a fresh appeal to the delegate's
time bound produces.  It is nonetheless the same number, and the reason is
worth naming: `HaltsExactly` pins the step count exactly, so the recorded cost
is *the* halting time and no other; and the round's own invariant pins the
clock's mark count to the tape, so the recorded step count is *the* count the
clock actually holds.  Both are recovered by uniqueness rather than by
threading, which is why the loop could be built before the bound existed.

The bound itself is then the expected shape: every round costs the round's
`80·A + 13·Σ|xs| + 13·r + Tm + 178`, the clock `A` never exceeds its start plus
`R·B`, and there are at most `R` rounds.
-/

namespace SipserGacsLautemann

open Classical

variable {tapes n states : Nat} {S : Type}

/-- A machine halts at one time only. -/
theorem HaltsExactly.unique {body : TypedMachine tapes S}
    {c : TypedConfiguration tapes S} {a b : Nat} {v w : Bool}
    (h₁ : HaltsExactly body c a v) (h₂ : HaltsExactly body c b w) : a = b := by
  by_contra hne
  rcases Nat.lt_or_ge a b with hlt | hge
  · have hn := h₂.fresh a hlt
    rw [h₁.halts] at hn
    simp at hn
  · have hlt : b < a := by omega
    have hn := h₁.fresh b hlt
    rw [h₂.halts] at hn
    simp at hn

/-- The clock's mark count is visible in its tape. -/
theorem clockCount_inj (a b : Nat) (Lc : List TapeSymbol)
    (h : cellsTape (List.replicate a (TapeSymbol.bit true) ++
          TapeSymbol.blank :: Lc) [] =
        cellsTape (List.replicate b (TapeSymbol.bit true) ++
          TapeSymbol.blank :: Lc) []) : a = b := by
  have hl : (List.replicate a (TapeSymbol.bit true) ++
      TapeSymbol.blank :: Lc).length =
      (List.replicate b (TapeSymbol.bit true) ++
        TapeSymbol.blank :: Lc).length :=
    congrArg List.length (congrArg Tape.left h)
  simpa using hl

/-- The delegate halts within `B` on every round's input. -/
def RoundHaltingBy (M : Machine 4 states) (xs : Fin 3 → List TapeSymbol)
    (B : Nat) : Prop :=
  ∀ (Ld : Fin 4 → List TapeSymbol) (m : Nat), ∃ Tm : Nat, ∃ v : Bool,
    Tm ≤ B ∧
    (∀ t, t < Tm → M.result
      ((M.step^[t]) ⟨M.start, roundTapes Ld xs m⟩).state = none) ∧
    M.result ((M.step^[Tm]) ⟨M.start, roundTapes Ld xs m⟩).state = some v

theorem roundHalting_of_by {M : Machine 4 states} {xs : Fin 3 → List TapeSymbol}
    {B : Nat} (h : RoundHaltingBy M xs B) : RoundHalting M xs := by
  intro Ld m
  obtain ⟨Tm, v, _, hlive, hhalt⟩ := h Ld m
  exact ⟨Tm, v, hlive, hhalt⟩

section

variable (L : RoundLayout n) (hL : L.Wf) (gd : Fin n)
  (hgc : gd ≠ L.clk) (hgd : ∀ j, gd ≠ L.dst j) (hgn : gd ≠ L.cnt)
  (hgs : ∀ i, gd ≠ L.src i) (hsc : ∀ i, L.src i ≠ L.clk)
  (hsn : ∀ i, L.src i ≠ L.cnt)
  (M : Machine 4 states)
  (xs Ls Rs : Fin 3 → List TapeSymbol) (Lclk Lg Rg : List TapeSymbol)
  (R : Nat) (hxs : ∀ i, ∀ x ∈ xs i, x ≠ TapeSymbol.blank)
  (hhalts : RoundHalting M xs)

/-- The delegate's step count at round `i`. -/
noncomputable def otime (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (i : Nat) :
    Nat :=
  (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i)).2.1

set_option maxHeartbeats 1000000 in
/-- **The recorded round agrees with a fresh appeal to the time bound.**  Both
the cost and the delegate's step count are recovered by uniqueness. -/
theorem ostep_bound (B : Nat) (hB : RoundHaltingBy M xs B)
    (t : OState L gd xs Ls Rs Lclk Lg Rg R) (i : Nat) (hti : t.idx = i)
    (hi : i < R) :
    (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).1 ≤ 80 * t.clock
      + 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
      + 13 * i + B + 178 ∧
    (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1 ≤ B := by
  classical
  subst hti
  obtain ⟨Ld, hdst⟩ := t.hinv.dstFun
  obtain ⟨Tm, v, hTmB, hlive, hhalt⟩ := hB Ld t.idx
  obtain ⟨cost, hcb, hhaltsB, hinv', hrv, hgl⟩ :=
    loopBody_spec L hL gd hgc hgd hgn hgs hsc hsn M t.tp xs Ls Rs Lclk Lg Rg
      R t.clock t.idx Tm Ld v hxs t.hinv hi t.hA
      (roundContent_size xs R t.clock t.idx (le_of_lt hi) t.hsz t.hszR)
      hdst hlive hhalt
  obtain ⟨hrec, htp, _, _⟩ := ostep_round L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t t.idx rfl hi
  have hcost : (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).1 = cost := hrec.unique hhaltsB
  have hclock : (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.clock = t.clock + (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1 := by
    rw [ostep_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t hi]
    exact (ostep_exists L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg
      R hxs hhalts t hi).choose_spec.2.1
  have htape : (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.tp =
      (((loopBody L gd M).step^[cost])
        ((loopBody L gd M).startCfg t.tp)).tape := by
    rw [htp, hcost]
  have h1 := (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.hinv.clk
  have h2 := hinv'.clk
  rw [htape] at h1
  rw [h1] at h2
  have := clockCount_inj _ _ Lclk h2.symm
  refine ⟨by omega, by omega⟩

set_option maxHeartbeats 1000000 in
/-- The clock grows by at most `B` a round. -/
theorem otraj_clock (B : Nat) (hB : RoundHaltingBy M xs B)
    (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (h0 : s₀.idx = 0)
    (i : Nat) (hi : i ≤ R) :
    (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i).clock ≤ s₀.clock + i * B := by
  induction i with
  | zero => simp [otraj]
  | succ i ih =>
      have hle : i ≤ R := by omega
      have hilt : i < R := by omega
      have hidx := otraj_idx L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ h0 i hle
      have hlt' : (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i).idx < R := by rw [hidx]; exact hilt
      have hbd := (ostep_bound L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B hB (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i) i hidx hilt).2
      have hclock : (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ (i + 1)).clock =
          (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i).clock + (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i)).2.1 := by
        show (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i)).2.2.2.clock = _
        rw [ostep_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i) hlt']
        exact (ostep_exists L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk
          Lg Rg R hxs hhalts (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i) hlt').choose_spec.2.1
      have hih := ih hle
      have hmul : (i + 1) * B = i * B + B := by ring
      omega

set_option maxHeartbeats 1000000 in
/-- Every round costs at most the same amount. -/
theorem ocost_le (B : Nat) (hB : RoundHaltingBy M xs B)
    (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (h0 : s₀.idx = 0)
    (i : Nat) (hi : i < R) :
    ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i ≤ 80 * (s₀.clock + R * B)
      + 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
      + 13 * R + B + 178 := by
  have hidx := otraj_idx L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ h0 i (le_of_lt hi)
  have h1 := (ostep_bound L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B hB (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i) i hidx hi).1
  have h2 := otraj_clock L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B hB s₀ h0 i (le_of_lt hi)
  have h3 : i * B ≤ R * B := Nat.mul_le_mul_right B (le_of_lt hi)
  show (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i)).1 ≤ _
  omega

set_option maxHeartbeats 1000000 in
/-- **The scheduler is polynomial.**  It halts with the right answer inside a
bound built from the clock's start, the round count, the input lengths and the
delegate's own time bound. -/
theorem offsetLoop_cost (B : Nat) (hB : RoundHaltingBy M xs B)
    (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (h0 : s₀.idx = 0) (hR : 1 ≤ R) :
    ∃ cost : Nat,
      cost ≤ (R + 1) * (80 * (s₀.clock + R * B)
        + 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
        + 13 * R + B + 179) ∧
      HaltsExactly (offsetLoop L gd M)
        (TypedConfiguration.inLoop () (oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ 0)) cost
        (decide (∃ i, i < R ∧ oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i = true)) := by
  obtain ⟨rounds, hlt, hloop⟩ := offsetLoop_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ h0 hR
  refine ⟨_, ?_, hloop⟩
  set K := 80 * (s₀.clock + R * B)
    + 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
    + 13 * R + B + 178 with hK
  clear_value K
  have hall : ∀ i, i < rounds → ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i ≤ K := by
    intro i hi
    rw [hK]
    exact ocost_le L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B hB s₀ h0 i (by omega)
  have h1 := loopCost_le_of hall
  have h2 := ocost_le L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B hB s₀ h0 rounds hlt
  have h3 : rounds * (K + 1) ≤ R * (K + 1) :=
    Nat.mul_le_mul_right _ (by omega)
  rw [← hK] at h2
  calc loopCost (ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀) rounds + ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds
      ≤ rounds * (K + 1) + K := by omega
    _ ≤ R * (K + 1) + (K + 1) := by omega
    _ = (R + 1) * (K + 1) := (Nat.succ_mul R (K + 1)).symm
    _ = (R + 1) * (80 * (s₀.clock + R * B)
          + 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
          + 13 * R + B + 179) := by rw [hK]

end

end SipserGacsLautemann

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