Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_traj_m

Definition

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

Definition code
import Definitions.Def_sgl_clean_agree

/-!
# The trajectory, with the margin carried in the state

`RoundHalting` asks the delegate to halt on the round's tapes for *every*
possible debris.  A machine drawn from `DecidesInPolynomialTime` is constrained
only on clean tapes; on dirty ones it need not halt at all.  So the hypothesis
has to be weakened to the debris the loop actually produces — debris behind a
blank margin — and since it is a parameter of the trajectory's *definition*,
the margin has to live in the state rather than beside it.

That is the only change.  Everything else about a round is what it was: the
same body, the same invariant, the same costs.
-/

namespace SipserGacsLautemann

open Classical

variable {n states : Nat}

/-- The delegate halts on the round's tapes whenever the debris sits behind a
margin of `B` blanks. -/
def RoundHaltingM (M : Machine 4 states) (xs : Fin 3 → List TapeSymbol)
    (B : Nat) : Prop :=
  ∀ (Ld : Fin 4 → List TapeSymbol) (m : Nat),
    (∀ j, ∃ L' : List TapeSymbol,
      Ld j = List.replicate B TapeSymbol.blank ++ L') →
    ∃ Tm : Nat, ∃ v : Bool, Tm ≤ B ∧
      (∀ t, t < Tm → M.result
        ((M.step^[t]) ⟨M.start, roundTapes Ld xs m⟩).state = none) ∧
      M.result ((M.step^[Tm]) ⟨M.start, roundTapes Ld xs m⟩).state = some v

/-- The margin, read off the working tapes' left context. -/
theorem margin_of_dst (L : RoundLayout n) (B : Nat) (T : Fin n → Tape)
    (A : Nat) (hm : MarginAt L B T A) (Ld : Fin 4 → List TapeSymbol)
    (hdst : ∀ j, ((moveDir HeadMove.right)^[A + A]) (T (L.dst j)) =
      cellsTape (TapeSymbol.blank :: Ld j) []) :
    ∀ j, ∃ L' : List TapeSymbol,
      Ld j = List.replicate B TapeSymbol.blank ++ L' := by
  intro j
  obtain ⟨L', hL'⟩ := hm j
  refine ⟨L', ?_⟩
  have := (hdst j).symm.trans hL'
  have hleft := congrArg Tape.left this
  exact List.cons_injective hleft

/-- The round carrier, with the margin. -/
structure OStateM (L : RoundLayout n) (gd : Fin n)
    (xs Ls Rs : Fin 3 → List TapeSymbol) (Lclk Lg Rg : List TapeSymbol)
    (R B Q : Nat) : Type where
  clock : Nat
  idx : Nat
  tp : Fin n → Tape
  hA : 1 ≤ clock
  hsz : ∀ i : Fin 3, (xs i).length + 2 ≤ clock + clock
  hszR : R + 2 ≤ clock + clock
  hszB : Q + B + 2 ≤ clock + clock
  hinv : OffsetInv L gd xs Ls Rs Lclk Lg Rg R clock idx tp
  hmargin : MarginAt L B tp clock

set_option maxHeartbeats 1000000 in
/-- **One step of the trajectory, margin included.** -/
theorem ostep_existsM (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)
    (s : OStateM L gd xs Ls Rs Lclk Lg Rg R B Q) (hidx : s.idx < R) :
    ∃ p : Nat × Nat × Bool × OStateM L gd xs Ls Rs Lclk Lg Rg R B Q,
      p.1 ≤ 80 * s.clock + 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
        + 13 * s.idx + p.2.1 + 178 ∧
      p.2.1 ≤ B ∧
      p.2.2.2.clock = s.clock + p.2.1 ∧
      p.2.2.2.idx = s.idx + 1 ∧
      HaltsExactly (loopBody L gd M) ((loopBody L gd M).startCfg s.tp) p.1
        (decide (s.idx + 1 < R)) ∧
      p.2.2.2.tp = (((loopBody L gd M).step^[p.1])
        ((loopBody L gd M).startCfg s.tp)).tape ∧
      roundVerdict (((loopBody L gd M).step^[p.1])
        ((loopBody L gd M).startCfg s.tp)).state = p.2.2.1 ∧
      guideLeft (((loopBody L gd M).step^[p.1])
        ((loopBody L gd M).startCfg s.tp)).state = decide (s.idx + 1 < R) := by
  classical
  obtain ⟨Ld, hdst⟩ := s.hinv.dstFun
  obtain ⟨Tm, v, hTmB, hlive, hhalt⟩ := hhalts Ld s.idx
    (margin_of_dst L B s.tp s.clock s.hmargin Ld hdst)
  obtain ⟨cost, hcb, hhaltsB, hinv', hrv, hgl, hdstv⟩ :=
    loopBody_dst L hL gd hgc hgd hgn hgs hsc hsn M s.tp xs Ls Rs Lclk Lg Rg
      R s.clock s.idx Tm Ld v hxs s.hinv hidx s.hA
      (roundContent_size xs R s.clock s.idx (le_of_lt hidx) s.hsz s.hszR)
      hdst hlive hhalt
  have hmar : MarginAt L B
      ((((loopBody L gd M).step^[cost])
        ((loopBody L gd M).startCfg s.tp)).tape) (s.clock + Tm) := by
    intro j
    rw [hdstv j]
    refine delegate_leaves_skippable_blanks M
      ⟨M.start, roundTapes Ld xs s.idx⟩ j Tm Q
      ((s.clock + Tm) + (s.clock + Tm)) B ?_ ?_
    · rw [roundTapes_right_length]
      exact hQ s.idx j (le_of_lt hidx)
    · have := s.hszB
      omega
  refine ⟨⟨cost, Tm, v,
    { clock := s.clock + Tm
      idx := s.idx + 1
      tp := (((loopBody L gd M).step^[cost])
        ((loopBody L gd M).startCfg s.tp)).tape
      hA := by have := s.hA; omega
      hsz := by intro i; have := s.hsz i; omega
      hszR := by have := s.hszR; omega
      hszB := by have := s.hszB; omega
      hinv := hinv'
      hmargin := hmar }⟩, hcb, hTmB, rfl, rfl, hhaltsB, rfl, hrv, hgl⟩

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