Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_sched_layout

Definition

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

Definition code
import Definitions.Def_sgl_prologue

/-!
# The scheduler's tape assignment

Ten tapes: three inputs, four the delegate works on, a clock, a counter, and a
guide.  `stdLayout` had nine — the guide is the tenth, and it has to be its own
tape because it is consumed as the loop runs while every other role must
survive to the next round.

The prologue's seven-role index is the same tapes under different names: its
worker is the first working tape, which the normalising walk never moves.
-/

namespace SipserGacsLautemann

/-- The layout the scheduler runs on. -/
def schedLayout : RoundLayout 10 where
  src := fun i => ⟨i.val, by omega⟩
  dst := fun j => ⟨3 + j.val, by omega⟩
  clk := ⟨7, by omega⟩
  cnt := ⟨8, by omega⟩

/-- The guide. -/
def schedGuide : Fin 10 := ⟨9, by omega⟩

/-- The prologue's roles, on this layout: three inputs, clock, guide, counter,
and a working tape to stand in as the normalising walk's idle partner. -/
def schedIdx : Fin 7 → Fin 10
  | 0 => ⟨0, by omega⟩
  | 1 => ⟨1, by omega⟩
  | 2 => ⟨2, by omega⟩
  | 3 => ⟨7, by omega⟩
  | 4 => ⟨9, by omega⟩
  | 5 => ⟨8, by omega⟩
  | 6 => ⟨3, by omega⟩

theorem schedIdx_injective : Function.Injective schedIdx := by
  intro a b hab
  fin_cases a <;> fin_cases b <;> simp_all [schedIdx] <;>
    exact absurd (congrArg Fin.val hab) (by decide)

theorem schedLayout_wf : schedLayout.Wf := by
  refine ⟨?_, ?_, ?_, ?_, ?_⟩
  · intro a b hab
    have := congrArg Fin.val hab
    simp [schedLayout] at this
    exact Fin.ext (by omega)
  · intro j hc
    have := congrArg Fin.val hc
    simp [schedLayout] at this
    omega
  · intro j hc
    have := congrArg Fin.val hc
    simp [schedLayout] at this
    omega
  · intro i j hc
    have := congrArg Fin.val hc
    simp [schedLayout] at this
    omega
  · intro hc
    have := congrArg Fin.val hc
    simp [schedLayout] at this

theorem schedLayout_src_clk : ∀ i, schedLayout.src i ≠ schedLayout.clk := by
  intro i hc
  have := congrArg Fin.val hc
  simp [schedLayout] at this
  omega

theorem schedLayout_src_cnt : ∀ i, schedLayout.src i ≠ schedLayout.cnt := by
  intro i hc
  have := congrArg Fin.val hc
  simp [schedLayout] at this
  omega

theorem schedGuide_clk : schedGuide ≠ schedLayout.clk := by
  intro hc
  have := congrArg Fin.val hc
  simp [schedGuide, schedLayout] at this

theorem schedGuide_cnt : schedGuide ≠ schedLayout.cnt := by
  intro hc
  have := congrArg Fin.val hc
  simp [schedGuide, schedLayout] at this

theorem schedGuide_dst : ∀ j, schedGuide ≠ schedLayout.dst j := by
  intro j hc
  have := congrArg Fin.val hc
  simp [schedGuide, schedLayout] at this
  omega

theorem schedGuide_src : ∀ i, schedGuide ≠ schedLayout.src i := by
  intro i hc
  have := congrArg Fin.val hc
  simp [schedGuide, schedLayout] at this
  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