Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_offset_records

Definition

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

Definition code
import Definitions.Def_sgl_offset_traj

/-!
# The trajectory, and the loop's per-round records

`ostep` picks one round's data by choice and `otraj` iterates it.  Past round
`R` the step is the identity, so the trajectory is total without the carrier
having to be defined at a round the invariant cannot reach.

`offsetRound_record` is then the `LoopRound` the loop wants, for any round that
both rejects and still has offsets left.  Those two conditions are exactly the
loop's own stopping test read backwards, which is what makes the record and the
machine agree by construction rather than by a matching argument.
-/

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)

/-- One round's data, chosen; the identity past the last round. -/
noncomputable def ostep (s : OState L gd xs Ls Rs Lclk Lg Rg R) :
    Nat × Nat × Bool × OState L gd xs Ls Rs Lclk Lg Rg R :=
  if h : s.idx < R then
    (ostep_exists L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R
      hxs hhalts s h).choose
  else (0, 0, false, s)

theorem ostep_spec (s : OState L gd xs Ls Rs Lclk Lg Rg R) (h : s.idx < R) :
    (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R
      hxs hhalts s) =
      (ostep_exists L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R
        hxs hhalts s h).choose := by
  rw [ostep, dif_pos h]

/-- The trajectory of carriers. -/
noncomputable def otraj (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) :
    Nat → OState L gd xs Ls Rs Lclk Lg Rg R
  | 0 => s₀
  | i + 1 => (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R
      hxs hhalts (otraj s₀ i)).2.2.2

/-- Round `i` of the trajectory is at index `i`, as long as it is a round that
actually runs. -/
theorem otraj_idx (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).idx = i := by
  induction i with
  | zero => exact h0
  | succ i ih =>
      have hle : i ≤ R := by omega
      have hidx := ih 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]; omega
      rw [otraj, ostep_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk
        Lg Rg R hxs hhalts _ hlt]
      have := (ostep_exists L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk
        Lg Rg R hxs hhalts _ hlt).choose_spec.2.2.1
      rw [this, hidx]

/-- The per-round cost. -/
noncomputable def ocost (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)).1

/-- The delegate's verdict at round `i`. -/
noncomputable def oans (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (i : Nat) :
    Bool :=
  (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.1

/-- The loop's configuration at round `i`. -/
noncomputable def oconfig (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (i : Nat) :=
  (loopBody L gd M).startCfg
    (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R
      hxs hhalts s₀ i).tp

/-! ## What one round of the trajectory records -/

set_option maxHeartbeats 1000000 in
/-- One chosen round, with the index named.  Substituting the index rather
than rewriting it is what keeps the dependent `choose` term well typed. -/
theorem ostep_round (t : OState L gd xs Ls Rs Lclk Lg Rg R) (i : Nat)
    (hti : t.idx = i) (hi : i < R) :
    HaltsExactly (loopBody L gd M) ((loopBody L gd M).startCfg t.tp)
      (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).1 (decide (i + 1 < R)) ∧
    (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^[(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).1])
        ((loopBody L gd M).startCfg t.tp)).tape ∧
    roundVerdict ((((loopBody L gd M).step^[(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).1])
      ((loopBody L gd M).startCfg t.tp))).state = (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.1 ∧
    guideLeft ((((loopBody L gd M).step^[(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).1])
      ((loopBody L gd M).startCfg t.tp))).state = decide (i + 1 < R) := by
  subst hti
  rw [ostep_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t hi]
  have hch := (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
  exact ⟨hch.2.2.2.1, hch.2.2.2.2.1, hch.2.2.2.2.2.1, hch.2.2.2.2.2.2⟩

/-- The same, along the trajectory. -/
theorem otraj_round (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (h0 : s₀.idx = 0)
    (i : Nat) (hi : i < R) :
    HaltsExactly (loopBody L gd M) (oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i) (ocost L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i)
      (decide (i + 1 < R)) ∧
    (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ (i + 1)).tp =
      (((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₀ i]) (oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i)).tape ∧
    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₀ i])
      (oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i))).state = oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i ∧
    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₀ i])
      (oconfig L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i))).state = decide (i + 1 < R) :=
  ostep_round 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) i (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)) hi

/-- **A round of the loop.**  Any round that rejects and still has offsets left
is a `LoopRound` for the scheduler. -/
theorem offset_record (s₀ : OState L gd xs Ls Rs Lclk Lg Rg R) (h0 : s₀.idx = 0)
    (i : Nat) (hi : i + 1 < R) (hrej : oans L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ i = false) :
    LoopRound (fun _ : Unit => loopBody L gd M) (fun _ _ => ())
      (fun _ b => roundVerdict b || !(guideLeft 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₀) i := 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 i (by omega)
  refine ⟨⟨_, hhalt⟩, ?_, rfl, ?_⟩
  · rw [hrv, hgl, hrej, decide_eq_true hi]
    rfl
  · show (loopBody L gd M).startCfg (otraj L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts s₀ (i + 1)).tp = _
    rw [htp]
    rfl

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