Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_body_spec

Definition

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

Definition code
import Definitions.Def_sgl_body_tapes

/-!
# One loop body, end to end

Four stages chained with `chainStepC`: the round, the bump, the guide step, the
test.  What makes this more than a chain is that the body must report *two*
answers — the delegate's verdict and whether offsets remain — and a composition
only carries its last stage's verdict.  The second answer is recovered from the
terminal state by peeling the `andThen` layers, which is what `loopBody_reads'`
does.

The cost is the round's plus eight: one step for the composition's own
dispatch at each of the three joins, three for the bump, one for the guide step
and one for the test.
-/

namespace SipserGacsLautemann

open Classical

variable {n states : Nat}

set_option maxHeartbeats 4000000 in
/-- **One body of the offset scheduler.**  From the invariant at round `r`, the
body halts reporting whether offsets remain, its terminal state carries the
delegate's verdict, and its tapes satisfy the invariant at round `r + 1`. -/
theorem loopBody_spec (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) (T : Fin n → Tape)
    (xs Ls Rs : Fin 3 → List TapeSymbol) (Lclk Lg Rg : List TapeSymbol)
    (R A r Tm : Nat) (Ld : Fin 4 → List TapeSymbol) (v : Bool)
    (hxs : ∀ i, ∀ x ∈ xs i, x ≠ TapeSymbol.blank)
    (hinv : OffsetInv L gd xs Ls Rs Lclk Lg Rg R A r T)
    (hr : r < R) (hA : 1 ≤ A)
    (hsize : ∀ j, (roundContent xs r j).length + 2 ≤ A + A)
    (hdst : ∀ j, ((moveDir HeadMove.right)^[A + A]) (T (L.dst j)) =
      cellsTape (TapeSymbol.blank :: Ld j) [])
    (hlive : ∀ m, m < Tm → M.result
      ((M.step^[m]) ⟨M.start, roundTapes Ld xs r⟩).state = none)
    (hhalt : M.result
      ((M.step^[Tm]) ⟨M.start, roundTapes Ld xs r⟩).state = some v) :
    ∃ cost : Nat,
      cost ≤ 80 * A + 13 * ((xs 0).length + (xs 1).length + (xs 2).length)
        + 13 * r + Tm + 178 ∧
      HaltsExactly (loopBody L gd M) ((loopBody L gd M).startCfg T) cost
        (decide (r + 1 < R)) ∧
      OffsetInv L gd xs Ls Rs Lclk Lg Rg R (A + Tm) (r + 1)
        (((loopBody L gd M).step^[cost]) ((loopBody L gd M).startCfg T)).tape ∧
      roundVerdict (((loopBody L gd M).step^[cost])
        ((loopBody L gd M).startCfg T)).state = v ∧
      guideLeft (((loopBody L gd M).step^[cost])
        ((loopBody L gd M).startCfg T)).state = decide (r + 1 < R) := by
  classical
  have hlen : (List.replicate r (TapeSymbol.bit true)).length = r := by simp
  have hcm : ∀ x ∈ List.replicate r (TapeSymbol.bit true),
      x ≠ TapeSymbol.blank := by
    intro x hx
    rw [List.eq_of_mem_replicate hx]
    simp
  -- 1. the round
  obtain ⟨c1, hc1b, g1, s1⟩ := offsetRound_specB L hL hsc M T A Lclk xs Ls Rs
    (List.replicate r (TapeSymbol.bit true))
    (List.replicate (R - r) TapeSymbol.blank) [] Ld Tm v hxs hcm
    hinv.clk hinv.src hinv.cnt hdst (by rw [hlen]; exact hlive)
    (by rw [hlen]; exact hhalt)
  rw [hlen] at hc1b s1
  set W := ((M.step^[Tm]) ⟨M.start, roundTapes Ld xs r⟩).tape with hW
  set T1 := clockTapesL L.sel L.clk T W (roundClockLeft A Lclk) Tm with hT1
  have hnosel : ∀ i : Fin n, (∀ j, L.dst j ≠ i) → ¬ ∃ j, L.sel j = i := by
    intro i hi hex
    obtain ⟨j, hj⟩ := hex
    exact hi j hj
  -- 2. the counter is where the round left it
  have hT1cnt : T1 L.cnt = cellsTape
      (TapeSymbol.blank :: List.replicate (R - r) TapeSymbol.blank)
      (List.replicate r (TapeSymbol.bit true) ++ [TapeSymbol.blank]) := by
    rw [hT1, clockTapesL_outer L.sel L.clk T W _ Tm L.cnt
      (fun h => hL.clk_cnt h.symm) (hnosel _ (fun j => hL.cnt_dst j))]
    exact hinv.cnt
  obtain ⟨g2, s2⟩ := bumpCounter_spec L.cnt r
    (List.replicate (R - r) TapeSymbol.blank) [] T1 hT1cnt
  set T2 := Function.update T1 L.cnt
    (cellsTape (List.replicate (R - r) TapeSymbol.blank)
      (List.replicate (r + 1) (TapeSymbol.bit true) ++
        TapeSymbol.blank :: [])) with hT2
  -- 3. the guide has not moved yet
  have hT2gd : T2 gd = T gd := by
    rw [hT2, Function.update_of_ne hgn, hT1,
      clockTapesL_outer L.sel L.clk T W _ Tm gd hgc
        (hnosel _ (fun j => fun hcon => hgd j hcon.symm))]
  have g3 := moveUpTo_spec gd 1 HeadMove.right (by omega) T2
  set T3 := Function.update T2 gd (moveDir HeadMove.right (T gd)) with hT3
  have s3 : (((moveUpTo gd 1 HeadMove.right).step^[1])
      ((moveUpTo gd 1 HeadMove.right).startCfg T2)).tape = T3 := by
    rw [moveUpTo_tape gd 1 HeadMove.right (by omega) T2, hT3,
      Function.iterate_one, hT2gd]
  -- 4. the invariant one round on, and what the test reads
  have hinv3 : OffsetInv L gd xs Ls Rs Lclk Lg Rg R (A + Tm) (r + 1) T3 :=
    offsetInv_succ L hL gd hgc hgd hgn hgs hsc hsn xs Ls Rs Lclk Lg Rg
      R A r Tm T Ld M hinv hr hA hsize T3 (by rw [hT3, hT2, hT1])
  have hread : notBlankAt gd (fun i => (T3 i).head) = decide (r + 1 < R) :=
    guide_test L gd xs Ls Rs Lclk Lg Rg R (A + Tm) r T3 hinv3
  have g4 := TypedMachine.test_spec (notBlankAt gd) T3
  rw [hread] at g4
  -- 5. the chain
  have k3 := chainStepC g3 s3 g4
  have k2 := chainStepC g2 s2 k3.1
  have k1 := chainStepC g1 s1 k2.1
  have hfin := k1.2
  rw [show ((offsetRound L M).andThen fun _ =>
      (bumpCounter L.cnt).andThen fun _ =>
        (moveUpTo gd 1 HeadMove.right).andThen fun _ =>
          TypedMachine.test (notBlankAt gd)) = loopBody L gd M from rfl] at hfin
  have hIR : ∀ {S₁ S₂ : Type} (b : Bool) (c : TypedConfiguration n S₂),
      (TypedConfiguration.inRight (S₁ := S₁) b c).tape = c.tape :=
    fun _ _ => rfl
  have htape : (((loopBody L gd M).step^[c1 + 1 + (1 + 1 + 1 + 1 + (1 + 1 + 1))])
      ((loopBody L gd M).startCfg T)).tape = T3 := by
    rw [hfin, hIR, k2.2, hIR, k3.2, hIR, TypedMachine.test_tape]
  have hpeel := loopBody_reads' (S₁ := Fin states) v true true
    (decide (r + 1 < R)) _ _ _ k3.2 k2.2
    (by rw [test_state]; exact congrArg some hread)
  refine ⟨c1 + 1 + (1 + 1 + 1 + 1 + (1 + 1 + 1)), by omega, k1.1, ?_, ?_, ?_⟩
  · rw [htape]; exact hinv3
  · rw [hfin]; exact hpeel.1
  · rw [hfin]; exact hpeel.2

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