Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_scheduler

Definition

by Henry Yuen · Jul 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

Definition code
import Definitions.Def_sgl_prologue_cost

/-!
# The scheduler

The prologue and the loop, joined.  No bridge is needed between them: a
`loopState`'s start state is the pair of its initial carry and its body's start
state, and `inLoop` builds exactly that configuration, so the loop's own
`startCfg` on the prologue's output tapes *is* the configuration the loop's
specification begins from.

What comes out is a machine that, given three inputs on their tapes and seven
blank tapes, answers whether the delegate accepts at any offset up to the third
input's length — in time linear in the inputs plus the loop's own bound.
-/

namespace SipserGacsLautemann

open Classical

variable {states : Nat}

/-- The three inputs, as a family. -/
def schedInputs (x0 x1 x2 : List TapeSymbol) : Fin 3 → List TapeSymbol :=
  fun i => if i.val = 0 then x0 else if i.val = 1 then x1 else x2

/-- Prologue, then loop. -/
noncomputable def scheduler (M : Machine 4 states) :=
  (prologue (schedIdx 0) (schedIdx 1) (schedIdx 2) (schedIdx 3) (schedIdx 4)
    (schedIdx 5) (schedIdx 6)).andThen fun _ =>
      offsetLoop schedLayout schedGuide M

set_option maxHeartbeats 4000000 in
/-- **The scheduler decides the bounded existential.** -/
theorem scheduler_spec (M : Machine 4 states) (B : Nat) (ans : Nat → Bool)
    (x0 x1 x2 : List TapeSymbol) (T : Fin 10 → Tape)
    (hn0 : ∀ c ∈ x0, c ≠ TapeSymbol.blank)
    (hn1 : ∀ c ∈ x1, c ≠ TapeSymbol.blank)
    (hn2 : ∀ c ∈ x2, c ≠ TapeSymbol.blank)
    (hU : RoundUniform M (schedInputs x0 x1 x2) B ans)
    (hx0 : T (schedIdx 0) = cellsTape [] x0)
    (hx1 : T (schedIdx 1) = cellsTape [] x1)
    (hx2 : T (schedIdx 2) = cellsTape [] x2)
    (hclk : T (schedIdx 3) = cellsTape [] [])
    (hgd : T (schedIdx 4) = cellsTape [] [])
    (hcnt : T (schedIdx 5) = cellsTape [] [])
    (hdst : ∀ j, T (schedLayout.dst j) = cellsTape [] []) :
    ∃ cost : Nat,
      cost ≤ 50 * (x0.length + x1.length + x2.length) + 201 +
        (x2.length + 1 + 1) *
          (80 * ((x2.length + (x1.length + (x0.length + 2)))
            + (x2.length + 1) * B)
            + 13 * (x0.length + x1.length + x2.length)
            + 13 * (x2.length + 1) + B + 179) ∧
      HaltsExactly (scheduler M) ((scheduler M).startCfg T) cost
        (decide (∃ i, i < x2.length + 1 ∧ ans i = true)) := by
  classical
  set xs := schedInputs x0 x1 x2 with hxs
  set R := x2.length + 1 with hR
  set A := x2.length + (x1.length + (x0.length + 2)) with hA
  obtain ⟨c1, T', hb1, g1, t1, e0, e1, e2, eclk, egd, ecnt, eoth⟩ :=
    prologue_specB schedIdx schedIdx_injective x0 x1 x2 T hn0 hn1 hn2
      hx0 hx1 hx2 hclk hgd hcnt
  have hdisj : ∀ (j : Fin 4), schedLayout.dst j ≠ schedIdx 0 ∧
      schedLayout.dst j ≠ schedIdx 1 ∧ schedLayout.dst j ≠ schedIdx 2 ∧
      schedLayout.dst j ≠ schedIdx 3 ∧ schedLayout.dst j ≠ schedIdx 4 ∧
      schedLayout.dst j ≠ schedIdx 5 := by
    intro j
    refine ⟨?_, ?_, ?_, ?_, ?_, ?_⟩ <;>
      (intro hc
       have := congrArg Fin.val hc
       simp [schedLayout, schedIdx] at this
       try omega)
  have hnbx : ∀ i, ∀ c ∈ xs i, c ≠ TapeSymbol.blank := by
    intro i
    fin_cases i
    · exact hn0
    · exact hn1
    · exact hn2
  have hinv : OffsetInv schedLayout schedGuide xs (fun _ => []) (fun _ => [])
      [] [] [] R A 0 T' := by
    refine offsetInv_zero schedLayout schedGuide xs R A T' (by omega) eclk
      ?_ ?_ ?_ egd
    · intro i
      fin_cases i
      · exact e0
      · exact e1
      · exact e2
    · exact ecnt
    · intro j
      obtain ⟨d0, d1, d2, d3, d4, d5⟩ := hdisj j
      rw [eoth _ d0 d1 d2 d3 d4 d5]
      exact hdst j
  set s₀ : OState schedLayout schedGuide xs (fun _ => []) (fun _ => [])
      [] [] [] R :=
    { clock := A, idx := 0, tp := T', hA := by omega
      hsz := by intro i; fin_cases i <;> simp [hxs, schedInputs] <;> omega
      hszR := by omega
      hinv := hinv } with hs₀
  obtain ⟨c2, hb2, g2⟩ := offsetLoop_answer schedLayout schedLayout_wf
    schedGuide schedGuide_clk schedGuide_dst schedGuide_cnt schedGuide_src
    schedLayout_src_clk schedLayout_src_cnt M xs (fun _ => []) (fun _ => [])
    [] [] [] R hnbx
    (roundHalting_of_by (roundHaltingBy_of_uniform hU)) B ans hU s₀ rfl
    (by omega)
  have g2' : HaltsExactly (offsetLoop schedLayout schedGuide M)
      ((offsetLoop schedLayout schedGuide M).startCfg T') c2
      (decide (∃ i, i < R ∧ ans i = true)) := g2
  have hclock : s₀.clock = A := rfl
  have hxs0 : xs 0 = x0 := rfl
  have hxs1 : xs 1 = x1 := rfl
  have hxs2 : xs 2 = x2 := rfl
  rw [hclock, hxs0, hxs1, hxs2] at hb2
  refine ⟨_, ?_, (chainStepC g1 t1 g2').1⟩
  omega

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