Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_offset_margin

Definition

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

Definition code
import Definitions.Def_sgl_body_dst

/-!
# The trajectory's working tapes

The same recovery as for the cost and the verdict: the round the trajectory
recorded and a fresh appeal to the delegate halt at the same step, so they have
the same tapes, so the working roles carry the delegate's own output.  Nothing
new is proved about the loop — the fact was always true of it, and this is the
statement that says so.

With that, the next round's skip can be measured.  The delegate's output is no
longer than its input plus its running time, so a skip of `2A` overshoots it by
`2A − |content| − Tm`, and the size side-condition is exactly what turns that
into a usable margin.
-/

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 recorded round's working tapes are the delegate's**, at the
delegate's own step count — which the round's invariant pins to the clock. -/
theorem ostep_dst (B : Nat) (hB : RoundHaltingBy M xs B)
    (t : OState L gd xs Ls Rs Lclk Lg Rg R) (i : Nat) (hti : t.idx = i)
    (hi : i < R) :
    ∃ Ld : Fin 4 → List TapeSymbol,
      (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1 ≤ B ∧
      ∀ j, (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 (L.dst j) =
        ((M.step^[(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1])
          ⟨M.start, roundTapes Ld xs i⟩).tape j := by
  classical
  subst hti
  obtain ⟨Ld, hdst⟩ := t.hinv.dstFun
  obtain ⟨Tm, v, hTmB, hlive, hhalt⟩ := hB Ld t.idx
  obtain ⟨cost, hcb, hhaltsB, hinv', hrv, hgl, hdstv⟩ :=
    loopBody_dst L hL gd hgc hgd hgn hgs hsc hsn M t.tp xs Ls Rs Lclk Lg Rg
      R t.clock t.idx Tm Ld v hxs t.hinv hi t.hA
      (roundContent_size xs R t.clock t.idx (le_of_lt hi) t.hsz t.hszR)
      hdst hlive hhalt
  obtain ⟨hrec, htp, _, _⟩ := ostep_round L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t t.idx rfl hi
  have hcost : (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).1 = cost := hrec.unique hhaltsB
  have hval : (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^[cost])
      ((loopBody L gd M).startCfg t.tp)).tape := by
    rw [htp, hcost]
  have hclock : (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.clock = t.clock + (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1 := by
    rw [ostep_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t hi]
    exact (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.2.1
  have h1 := (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.hinv.clk
  have h2 := hinv'.clk
  rw [hval] at h1
  rw [h1] at h2
  have heq := clockCount_inj _ _ Lclk h2.symm
  have hTmeq : (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1 = Tm := by omega
  refine ⟨Ld, by omega, fun j => ?_⟩
  rw [hval, hTmeq]
  exact hdstv j

/-- **The margin the next skip leaves.**  The delegate's output is no longer
than its input plus its running time, so a size condition with `B` to spare
turns the next round's skip into a blank margin of `B`. -/
theorem ostep_margin (B : Nat) (hB : RoundHaltingBy M xs B)
    (Q : Nat) (hQ : ∀ m j, m ≤ R → (roundContent xs m j).length ≤ Q)
    (t : OState L gd xs Ls Rs Lclk Lg Rg R) (i : Nat) (hti : t.idx = i)
    (hi : i < R) (hsize : Q + B + 2 ≤ t.clock + t.clock) :
    ∀ j, ∃ L' : List TapeSymbol,
      ((moveDir HeadMove.right)^[(ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.clock +
          (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.clock])
        ((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 (L.dst j)) =
        cellsTape (TapeSymbol.blank ::
          (List.replicate B TapeSymbol.blank ++ L')) [] := by
  classical
  obtain ⟨Ld, hTmB, hval⟩ := ostep_dst L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts B hB t i hti hi
  have hclock : (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.2.2.clock = t.clock + (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1 := by
    rw [ostep_spec L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t (by rw [hti]; exact hi)]
    exact (ostep_exists L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg
      R hxs hhalts t (by rw [hti]; exact hi)).choose_spec.2.1
  intro j
  rw [hval j, hclock]
  refine delegate_leaves_skippable_blanks M ⟨M.start, roundTapes Ld xs i⟩ j
    ((ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1) Q
    ((t.clock + (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1) + (t.clock + (ostep L hL gd hgc hgd hgn hgs hsc hsn M xs Ls Rs Lclk Lg Rg R hxs hhalts t).2.1)) B ?_ ?_
  · rw [roundTapes_right_length]
    exact hQ i j (le_of_lt hi)
  · omega

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