Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_offset_loop_spec

Definition

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

Definition code
import Definitions.Def_sgl_offset_records

/-!
# The scheduler halts, and reports whether any offset accepted

The loop stops on the first round that accepts, or on the last round if none
does.  Both cases are the same `loopState_spec_v` application; they differ only
in which disjunct of the stopping test fires — the delegate's verdict in the
first case, the exhausted guide in the second.

The verdict the loop reports is the delegate's answer at the round it stopped
on, and that answer is `true` exactly when some offset accepts: an accepting
round halts the loop immediately, and if none accepts the last round's `false`
is what stands.
-/

namespace SipserGacsLautemann

open Classical

variable {n states : Nat}

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)

set_option maxHeartbeats 1000000 in
/-- **The loop, at a stopping round.**  Given a round that nothing before it
accepts and that stops the loop when reached, the scheduler halts there with
that round's verdict. -/
theorem offsetLoop_at (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (h0 : s₀.idx = 0)
    (rounds : Nat) (hlt : rounds < R)
    (hbefore : ∀ i, i < rounds → oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i = false)
    (hfire : oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds = true ∨ rounds + 1 = R) :
    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))
      (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)
      (oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds) := by
  obtain ⟨hhalt, htp, hrv, hgl⟩ := otraj_round L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ h0 rounds hlt
  have hstopB : (roundVerdict (((loopBody L gd M).step^[ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds])
        (oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds)).state ||
      !guideLeft (((loopBody L gd M).step^[ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds])
        (oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds)).state) = true := by
    rw [hrv, hgl]
    rcases hfire with h | h
    · rw [h]
      rfl
    · rw [decide_eq_false (by omega : ¬ rounds + 1 < R)]
      simp
  have hmain := TypedMachine.loopState_spec_v
    (fun _ : Unit => loopBody L gd M) (fun _ _ => ())
    (fun _ b => roundVerdict b || !(guideLeft b))
    (fun _ b => roundVerdict b) ()
    (fun _ : Nat => ()) (oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀) (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) (decide (rounds + 1 < R))
    (fun i hi => offset_record L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ h0 i (by omega) (hbefore i hi))
    hhalt hstopB
  have hmain' : 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))
      (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)
      (roundVerdict (((loopBody L gd M).step^[ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds])
        (oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ rounds)).state) := hmain
  rw [hrv] at hmain'
  exact hmain'

set_option maxHeartbeats 1000000 in
/-- **The scheduler.**  It halts, and its verdict is whether some offset below
`R` is accepted by the delegate. -/
theorem offsetLoop_spec (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R)
    (h0 : s₀.idx = 0) (hR : 1 ≤ R) :
    ∃ rounds : Nat, rounds < R ∧
      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))
        (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)
        (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
  classical
  by_cases hacc : ∃ 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
  · obtain ⟨hlt, hans⟩ := Nat.find_spec hacc
    have hbef : ∀ i, i < Nat.find hacc → oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i = false := by
      intro i hi
      have hmin := Nat.find_min hacc hi
      have hiR : i < R := by omega
      cases hb : oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i with
      | false => rfl
      | true => exact absurd ⟨hiR, hb⟩ hmin
    have hloop := offsetLoop_at L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ h0 (Nat.find hacc) hlt hbef (Or.inl hans)
    rw [hans] at hloop
    refine ⟨Nat.find hacc, hlt, ?_⟩
    rw [decide_eq_true hacc]
    exact hloop
  · have hans : oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ (R - 1) = false := by
      cases hb : oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ (R - 1) with
      | false => rfl
      | true => exact absurd ⟨R - 1, by omega, hb⟩ hacc
    have hbef : ∀ i, i < R - 1 → oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i = false := by
      intro i hi
      cases hb : oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i with
      | false => rfl
      | true => exact absurd ⟨i, by omega, hb⟩ hacc
    have hloop := offsetLoop_at L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ h0 (R - 1) (by omega) hbef
      (Or.inr (by omega))
    rw [hans] at hloop
    refine ⟨R - 1, by omega, ?_⟩
    rw [decide_eq_false hacc]
    exact hloop

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