Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_prologue_cost

Definition

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

Definition code
import Definitions.Def_sgl_dig_costs

/-!
# What the prologue costs, end to end

The clock's stage is two marks and three tallies; the prologue is three inputs,
two origin markers, the clock and the guide.  Everything underneath now reports
an exact cost, so both totals are linear in the inputs' lengths and the bounds
are arithmetic.

The prologue's bound is deliberately loose.  It is a one-time linear cost
against a scheduler whose own bound is a product of the round count and the
delegate's time, so nothing is gained by tightening it, and a slack bound is
one less thing to re-derive if a stage changes.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

set_option maxHeartbeats 4000000 in
/-- **The clock's stage costs `9Σ|x| + 36`.** -/
theorem clockSetup_specB (s0 s1 s2 clk : Fin tapes)
    (h0 : s0 ≠ clk) (h1 : s1 ≠ clk) (h2 : s2 ≠ clk)
    (x0 x1 x2 L0 L1 L2 R0 R1 R2 : List TapeSymbol) (T : Fin tapes → Tape)
    (hn0 : ∀ c ∈ x0, c ≠ TapeSymbol.blank)
    (hn1 : ∀ c ∈ x1, c ≠ TapeSymbol.blank)
    (hn2 : ∀ c ∈ x2, c ≠ TapeSymbol.blank)
    (hs0 : T s0 = cellsTape (TapeSymbol.blank :: L0)
      (x0 ++ TapeSymbol.blank :: R0))
    (hs1 : T s1 = cellsTape (TapeSymbol.blank :: L1)
      (x1 ++ TapeSymbol.blank :: R1))
    (hs2 : T s2 = cellsTape (TapeSymbol.blank :: L2)
      (x2 ++ TapeSymbol.blank :: R2))
    (hclk : T clk = cellsTape [TapeSymbol.blank] []) :
    ∃ cost : Nat,
      cost ≤ 9 * (x0.length + x1.length + x2.length) + 36 ∧
      HaltsExactly (clockSetup s0 s1 s2 clk)
        ((clockSetup s0 s1 s2 clk).startCfg T) cost true ∧
      (((clockSetup s0 s1 s2 clk).step^[cost])
        ((clockSetup s0 s1 s2 clk).startCfg T)).tape =
        Function.update T clk
          (cellsTape (List.replicate
            (x2.length + (x1.length + (x0.length + 2))) (TapeSymbol.bit true)
            ++ [TapeSymbol.blank]) []) := by
  classical
  obtain ⟨gA, sA⟩ := writeMark_spec clk [TapeSymbol.blank] [] T hclk
  set TA := Function.update T clk
    (cellsTape (TapeSymbol.bit true :: [TapeSymbol.blank])
      ([] : List TapeSymbol).tail) with hTA
  have hTAclk : TA clk = cellsTape
      (List.replicate 1 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] := by
    rw [hTA, Function.update_self]
    simp
  obtain ⟨gB, sB⟩ := writeMark_spec clk
    (List.replicate 1 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] TA hTAclk
  set TB := Function.update TA clk
    (cellsTape (TapeSymbol.bit true ::
      (List.replicate 1 (TapeSymbol.bit true) ++ [TapeSymbol.blank]))
      ([] : List TapeSymbol).tail) with hTB
  have hTBclk : TB clk = cellsTape
      (List.replicate 2 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] := by
    rw [hTB, Function.update_self]
    simp [List.replicate_succ]
  have hTBs : ∀ (s : Fin tapes), s ≠ clk → TB s = T s := by
    intro s hs
    rw [hTB, Function.update_of_ne hs, hTA, Function.update_of_ne hs]
  obtain ⟨c1, hb1, g1, t1⟩ := tallyOnto_specB s0 clk h0 x0 L0 R0
    (List.replicate 2 (TapeSymbol.bit true) ++ [TapeSymbol.blank]) [] TB hn0
    (by rw [hTBs s0 h0]; exact hs0) hTBclk
  set T1 := Function.update TB clk
    (cellsTape (List.replicate x0.length (TapeSymbol.bit true) ++
      (List.replicate 2 (TapeSymbol.bit true) ++ [TapeSymbol.blank]))
      (([] : List TapeSymbol).drop x0.length)) with hT1
  have hT1clk : T1 clk = cellsTape
      (List.replicate (x0.length + 2) (TapeSymbol.bit true) ++
        [TapeSymbol.blank]) [] := by
    rw [hT1, Function.update_self, ← List.append_assoc, ← List.replicate_add]
    simp
  have hT1s : ∀ (s : Fin tapes), s ≠ clk → T1 s = T s := by
    intro s hs
    rw [hT1, Function.update_of_ne hs]
    exact hTBs s hs
  obtain ⟨c2, hb2, g2, t2⟩ := tallyOnto_specB s1 clk h1 x1 L1 R1
    (List.replicate (x0.length + 2) (TapeSymbol.bit true) ++
      [TapeSymbol.blank]) [] T1 hn1
    (by rw [hT1s s1 h1]; exact hs1) hT1clk
  set T2 := Function.update T1 clk
    (cellsTape (List.replicate x1.length (TapeSymbol.bit true) ++
      (List.replicate (x0.length + 2) (TapeSymbol.bit true) ++
        [TapeSymbol.blank]))
      (([] : List TapeSymbol).drop x1.length)) with hT2
  have hT2clk : T2 clk = cellsTape
      (List.replicate (x1.length + (x0.length + 2)) (TapeSymbol.bit true) ++
        [TapeSymbol.blank]) [] := by
    rw [hT2, Function.update_self, ← List.append_assoc, ← List.replicate_add]
    simp
  have hT2s : ∀ (s : Fin tapes), s ≠ clk → T2 s = T s := by
    intro s hs
    rw [hT2, Function.update_of_ne hs]
    exact hT1s s hs
  obtain ⟨c3, hb3, g3, t3⟩ := tallyOnto_specB s2 clk h2 x2 L2 R2
    (List.replicate (x1.length + (x0.length + 2)) (TapeSymbol.bit true) ++
      [TapeSymbol.blank]) [] T2 hn2
    (by rw [hT2s s2 h2]; exact hs2) hT2clk
  have k3 := chainStepC g2 t2 g3
  have k2 := chainStepC g1 t1 k3.1
  have k1 := chainStepC gB sB k2.1
  have k0 := chainStepC gA sA k1.1
  refine ⟨_, by omega, k0.1, ?_⟩
  have hfin := k0.2
  rw [k1.2, k2.2, k3.2] at hfin
  have hfin' : ((clockSetup s0 s1 s2 clk).step^[_])
      ((clockSetup s0 s1 s2 clk).startCfg T) = _ := hfin
  rw [hfin']
  show (((tallyOnto s2 clk).step^[c3])
    ((tallyOnto s2 clk).startCfg T2)).tape = _
  rw [t3]
  funext j
  by_cases hj : j = clk
  · subst hj
    rw [Function.update_self, Function.update_self, ← List.append_assoc,
      ← List.replicate_add]
    simp
  · rw [Function.update_of_ne hj, Function.update_of_ne hj]
    exact hT2s j hj


set_option maxHeartbeats 4000000 in
/-- **The prologue is linear in its inputs.** -/
theorem prologue_specB (idx : Fin 7 → Fin tapes) (hinj : Function.Injective idx)
    (x0 x1 x2 : List TapeSymbol) (T : Fin tapes → Tape)
    (hn0 : ∀ c ∈ x0, c ≠ TapeSymbol.blank)
    (hn1 : ∀ c ∈ x1, c ≠ TapeSymbol.blank)
    (hn2 : ∀ c ∈ x2, c ≠ TapeSymbol.blank)
    (hx0 : T (idx 0) = cellsTape [] x0)
    (hx1 : T (idx 1) = cellsTape [] x1)
    (hx2 : T (idx 2) = cellsTape [] x2)
    (hclk : T (idx 3) = cellsTape [] [])
    (hgd : T (idx 4) = cellsTape [] [])
    (hcnt : T (idx 5) = cellsTape [] []) :
    ∃ cost : Nat, ∃ T' : Fin tapes → Tape,
      cost ≤ 50 * (x0.length + x1.length + x2.length) + 200 ∧
      HaltsExactly (prologue (idx 0) (idx 1) (idx 2) (idx 3) (idx 4) (idx 5)
        (idx 6))
        ((prologue (idx 0) (idx 1) (idx 2) (idx 3) (idx 4) (idx 5)
          (idx 6)).startCfg T) cost true ∧
      (((prologue (idx 0) (idx 1) (idx 2) (idx 3) (idx 4) (idx 5)
        (idx 6)).step^[cost])
        ((prologue (idx 0) (idx 1) (idx 2) (idx 3) (idx 4) (idx 5)
          (idx 6)).startCfg T)).tape = T' ∧
      T' (idx 0) = cellsTape [TapeSymbol.blank] (x0 ++ [TapeSymbol.blank]) ∧
      T' (idx 1) = cellsTape [TapeSymbol.blank] (x1 ++ [TapeSymbol.blank]) ∧
      T' (idx 2) = cellsTape [TapeSymbol.blank] (x2 ++ [TapeSymbol.blank]) ∧
      T' (idx 3) = cellsTape (List.replicate
        (x2.length + (x1.length + (x0.length + 2))) (TapeSymbol.bit true)
        ++ [TapeSymbol.blank]) [] ∧
      T' (idx 4) = cellsTape []
        (List.replicate (x2.length + 1) (TapeSymbol.bit true) ++
          [TapeSymbol.blank]) ∧
      T' (idx 5) = cellsTape
        (List.replicate (x2.length + 2) TapeSymbol.blank) [] ∧
      (∀ j, j ≠ idx 0 → j ≠ idx 1 → j ≠ idx 2 → j ≠ idx 3 → j ≠ idx 4 →
        j ≠ idx 5 → T' j = T j) := by
  classical
  have hne : ∀ a b : Fin 7, a ≠ b → idx a ≠ idx b :=
    fun a b hab h => hab (hinj h)
  -- 1..3: the inputs
  obtain ⟨c1, hb1, g1, t1⟩ := inputPrep_specB (idx 0) (idx 6) (hne 0 6 (by decide))
    x0 T hn0 hx0
  set T1 := Function.update T (idx 0)
    (cellsTape [TapeSymbol.blank] (x0 ++ [TapeSymbol.blank])) with hT1
  obtain ⟨c2, hb2, g2, t2⟩ := inputPrep_specB (idx 1) (idx 6) (hne 1 6 (by decide))
    x1 T1 hn1 (by rw [hT1, Function.update_of_ne (hne 1 0 (by decide))]; exact hx1)
  set T2 := Function.update T1 (idx 1)
    (cellsTape [TapeSymbol.blank] (x1 ++ [TapeSymbol.blank])) with hT2
  obtain ⟨c3, hb3, g3, t3⟩ := inputPrep_specB (idx 2) (idx 6) (hne 2 6 (by decide))
    x2 T2 hn2 (by
      rw [hT2, Function.update_of_ne (hne 2 1 (by decide)), hT1,
        Function.update_of_ne (hne 2 0 (by decide))]
      exact hx2)
  set T3 := Function.update T2 (idx 2)
    (cellsTape [TapeSymbol.blank] (x2 ++ [TapeSymbol.blank])) with hT3
  have hT3o : ∀ j, j ≠ idx 0 → j ≠ idx 1 → j ≠ idx 2 → T3 j = T j := by
    intro j h0 h1 h2
    rw [hT3, Function.update_of_ne h2, hT2, Function.update_of_ne h1, hT1,
      Function.update_of_ne h0]
  -- 4, 5: the origin markers
  obtain ⟨g4, t4⟩ := prepTape_spec (idx 3) T3 []
    (by rw [hT3o (idx 3) (hne 3 0 (by decide)) (hne 3 1 (by decide))
      (hne 3 2 (by decide))]; exact hclk)
  set T4 := Function.update T3 (idx 3)
    (cellsTape [TapeSymbol.blank] ([] : List TapeSymbol)) with hT4
  obtain ⟨g5, t5⟩ := prepTape_spec (idx 4) T4 []
    (by
      rw [hT4, Function.update_of_ne (hne 4 3 (by decide)),
        hT3o (idx 4) (hne 4 0 (by decide)) (hne 4 1 (by decide))
          (hne 4 2 (by decide))]
      exact hgd)
  set T5 := Function.update T4 (idx 4)
    (cellsTape [TapeSymbol.blank] ([] : List TapeSymbol)) with hT5
  have h5x0 : T5 (idx 0) =
      cellsTape [TapeSymbol.blank] (x0 ++ [TapeSymbol.blank]) := by
    rw [hT5, Function.update_of_ne (hne 0 4 (by decide)), hT4,
      Function.update_of_ne (hne 0 3 (by decide)), hT3,
      Function.update_of_ne (hne 0 2 (by decide)), hT2,
      Function.update_of_ne (hne 0 1 (by decide)), hT1, Function.update_self]
  have h5x1 : T5 (idx 1) =
      cellsTape [TapeSymbol.blank] (x1 ++ [TapeSymbol.blank]) := by
    rw [hT5, Function.update_of_ne (hne 1 4 (by decide)), hT4,
      Function.update_of_ne (hne 1 3 (by decide)), hT3,
      Function.update_of_ne (hne 1 2 (by decide)), hT2, Function.update_self]
  have h5x2 : T5 (idx 2) =
      cellsTape [TapeSymbol.blank] (x2 ++ [TapeSymbol.blank]) := by
    rw [hT5, Function.update_of_ne (hne 2 4 (by decide)), hT4,
      Function.update_of_ne (hne 2 3 (by decide)), hT3, Function.update_self]
  have h5clk : T5 (idx 3) = cellsTape [TapeSymbol.blank] [] := by
    rw [hT5, Function.update_of_ne (hne 3 4 (by decide)), hT4,
      Function.update_self]
  have h5gd : T5 (idx 4) = cellsTape [TapeSymbol.blank] [] := by
    rw [hT5, Function.update_self]
  have h5cnt : T5 (idx 5) = cellsTape [] [] := by
    rw [hT5, Function.update_of_ne (hne 5 4 (by decide)), hT4,
      Function.update_of_ne (hne 5 3 (by decide)),
      hT3o (idx 5) (hne 5 0 (by decide)) (hne 5 1 (by decide))
        (hne 5 2 (by decide))]
    exact hcnt
  have h5o : ∀ j, j ≠ idx 0 → j ≠ idx 1 → j ≠ idx 2 → j ≠ idx 3 → j ≠ idx 4 →
      T5 j = T j := by
    intro j h0 h1 h2 h3 h4
    rw [hT5, Function.update_of_ne h4, hT4, Function.update_of_ne h3,
      hT3o j h0 h1 h2]
  -- 6: the clock
  obtain ⟨c6, hb6, g6, t6⟩ := clockSetup_specB (idx 0) (idx 1) (idx 2) (idx 3)
    (hne 0 3 (by decide)) (hne 1 3 (by decide)) (hne 2 3 (by decide))
    x0 x1 x2 [] [] [] [] [] [] T5 hn0 hn1 hn2 h5x0 h5x1 h5x2 h5clk
  set T6 := Function.update T5 (idx 3)
    (cellsTape (List.replicate (x2.length + (x1.length + (x0.length + 2)))
      (TapeSymbol.bit true) ++ [TapeSymbol.blank]) []) with hT6
  -- 7: the guide and the counter
  obtain ⟨c7, hb7, g7, t7⟩ := guideSetup_specB (idx 2) (idx 4) (idx 5)
    (hne 2 4 (by decide)) (hne 4 5 (by decide)) (hne 2 5 (by decide))
    x2 [] [] T6 hn2
    (by rw [hT6, Function.update_of_ne (hne 2 3 (by decide))]; exact h5x2)
    (by rw [hT6, Function.update_of_ne (hne 4 3 (by decide))]; exact h5gd)
    (by rw [hT6, Function.update_of_ne (hne 5 3 (by decide))]; exact h5cnt)
  set T7 := Function.update (Function.update T6 (idx 5)
    (cellsTape (List.replicate (x2.length + 2) TapeSymbol.blank) []))
    (idx 4) (cellsTape []
      (List.replicate (x2.length + 1) (TapeSymbol.bit true) ++
        [TapeSymbol.blank])) with hT7
  -- the chain
  have p6 := chainStepC g6 t6 g7
  have p5 := chainStepC g5 t5 p6.1
  have p4 := chainStepC g4 t4 p5.1
  have p3 := chainStepC g3 t3 p4.1
  have p2 := chainStepC g2 t2 p3.1
  have p1 := chainStepC g1 t1 p2.1
  have hIR : ∀ {S₁ S₂ : Type} (b : Bool) (c : TypedConfiguration tapes S₂),
      (TypedConfiguration.inRight (S₁ := S₁) b c).tape = c.tape :=
    fun _ _ => rfl
  refine ⟨_, T7, by omega, p1.1, ?_, ?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
  · have hfin : ((prologue (idx 0) (idx 1) (idx 2) (idx 3) (idx 4) (idx 5)
        (idx 6)).step^[_])
        ((prologue (idx 0) (idx 1) (idx 2) (idx 3) (idx 4) (idx 5)
          (idx 6)).startCfg T) = _ := p1.2
    rw [hfin, hIR, p2.2, hIR, p3.2, hIR, p4.2, hIR, p5.2, hIR, p6.2, hIR, t7]
  · rw [hT7, Function.update_of_ne (hne 0 4 (by decide)),
      Function.update_of_ne (hne 0 5 (by decide)), hT6,
      Function.update_of_ne (hne 0 3 (by decide))]
    exact h5x0
  · rw [hT7, Function.update_of_ne (hne 1 4 (by decide)),
      Function.update_of_ne (hne 1 5 (by decide)), hT6,
      Function.update_of_ne (hne 1 3 (by decide))]
    exact h5x1
  · rw [hT7, Function.update_of_ne (hne 2 4 (by decide)),
      Function.update_of_ne (hne 2 5 (by decide)), hT6,
      Function.update_of_ne (hne 2 3 (by decide))]
    exact h5x2
  · rw [hT7, Function.update_of_ne (hne 3 4 (by decide)),
      Function.update_of_ne (hne 3 5 (by decide)), hT6, Function.update_self]
  · rw [hT7, Function.update_self]
  · rw [hT7, Function.update_of_ne (hne 5 4 (by decide)),
      Function.update_self]
  · intro j h0 h1 h2 h3 h4 h5
    rw [hT7, Function.update_of_ne h4, Function.update_of_ne h5, hT6,
      Function.update_of_ne h3]
    exact h5o j h0 h1 h2 h3 h4

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