Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_records_m

Definition

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

Definition code
import Definitions.Def_sgl_traj_m

/-!
# The trajectory and its records, with the margin

The same definitions as before, over the margin-carrying carrier.  The proofs
are unchanged; only the hypothesis the delegate is held to has moved from "on
every debris" to "on debris behind a margin", and the carrier now supplies the
margin at each round.
-/

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 B Q : Nat) (hxs : ∀ i, ∀ x ∈ xs i, x ≠ TapeSymbol.blank)
  (hQ : ∀ m j, m ≤ R → (roundContent xs m j).length ≤ Q)
  (hhalts : RoundHaltingM M xs B)

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

theorem ostepM_spec (s : OStateM L gd xs Ls Rs Lclk Lg Rg R B Q)
    (h : s.idx < R) :
    (ostepM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s) = (ostep_existsM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s h).choose := by
  rw [ostepM, dif_pos h]

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

theorem otrajM_idx (s₀ : OStateM L gd xs Ls Rs Lclk Lg Rg R B Q)
    (h0 : s₀.idx = 0) (i : Nat) (hi : i ≤ R) :
    (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ 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 : (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i).idx < R := by rw [hidx]; omega
      rw [otrajM, ostepM_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts _ hlt]
      have := (ostep_existsM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts _ hlt).choose_spec.2.2.2.1
      rw [this, hidx]

/-- The per-round cost. -/
noncomputable def ocostM (s₀ : OStateM L gd xs Ls Rs Lclk Lg Rg R B Q)
    (i : Nat) : Nat := (ostepM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i)).1

/-- The delegate's verdict at round `i`. -/
noncomputable def oansM (s₀ : OStateM L gd xs Ls Rs Lclk Lg Rg R B Q)
    (i : Nat) : Bool := (ostepM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i)).2.2.1

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

set_option maxHeartbeats 1000000 in
/-- One chosen round, with the index named. -/
theorem ostepM_round (t : OStateM L gd xs Ls Rs Lclk Lg Rg R B Q) (i : Nat)
    (hti : t.idx = i) (hi : i < R) :
    HaltsExactly (loopBody L gd M) ((loopBody L gd M).startCfg t.tp)
      (ostepM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts t).1 (decide (i + 1 < R)) ∧
    (ostepM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts t).2.2.2.tp =
      (((loopBody L gd M).step^[(ostepM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts t).1])
        ((loopBody L gd M).startCfg t.tp)).tape ∧
    roundVerdict ((((loopBody L gd M).step^[(ostepM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts t).1])
      ((loopBody L gd M).startCfg t.tp))).state = (ostepM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts t).2.2.1 ∧
    guideLeft ((((loopBody L gd M).step^[(ostepM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts t).1])
      ((loopBody L gd M).startCfg t.tp))).state = decide (i + 1 < R) := by
  subst hti
  rw [ostepM_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts t hi]
  have hch := (ostep_existsM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts t hi).choose_spec
  exact ⟨hch.2.2.2.2.1, hch.2.2.2.2.2.1, hch.2.2.2.2.2.2.1,
    hch.2.2.2.2.2.2.2⟩

/-- The same, along the trajectory. -/
theorem otrajM_round (s₀ : OStateM L gd xs Ls Rs Lclk Lg Rg R B Q)
    (h0 : s₀.idx = 0) (i : Nat) (hi : i < R) :
    HaltsExactly (loopBody L gd M) (oconfigM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i) (ocostM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i)
      (decide (i + 1 < R)) ∧
    (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ (i + 1)).tp =
      (((loopBody L gd M).step^[ocostM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i])
        (oconfigM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i)).tape ∧
    roundVerdict ((((loopBody L gd M).step^[ocostM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i])
      (oconfigM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i))).state = oansM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i ∧
    guideLeft ((((loopBody L gd M).step^[ocostM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i])
      (oconfigM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i))).state = decide (i + 1 < R) :=
  ostepM_round L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i) i
    (otrajM_idx L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ h0 i (le_of_lt hi)) hi

/-- **A round of the loop.** -/
theorem offsetM_record (s₀ : OStateM L gd xs Ls Rs Lclk Lg Rg R B Q)
    (h0 : s₀.idx = 0) (i : Nat) (hi : i + 1 < R)
    (hrej : oansM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ i = false) :
    LoopRound (fun _ : Unit => loopBody L gd M) (fun _ _ => ())
      (fun _ b => roundVerdict b || !(guideLeft b))
      (fun _ : Nat => ()) (oconfigM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀) (ocostM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀) i := by
  obtain ⟨hhalt, htp, hrv, hgl⟩ := otrajM_round L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ hhalts s₀ h0 i (by omega)
  refine ⟨⟨_, hhalt⟩, ?_, rfl, ?_⟩
  · rw [hrv, hgl, hrej, decide_eq_true hi]
    rfl
  · show (loopBody L gd M).startCfg (otrajM L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R B Q hxs hQ 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