Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_guide_setup

Definition

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

Definition code
import Definitions.Def_sgl_counter_setup

/-!
# Setting the guide up, and widening the reservoir

The guide is a consumable tally of the offsets: one mark per cell of the third
input, plus one, so the loop runs `|xs 2| + 1` rounds and tries every offset
from `0` to `|xs 2|`.  `markBack` writes the tally and `bumpCounter` adds the
extra mark.

The order of the prologue's stages is forced by their shapes.  `markBack`
leaves its target with a blank explicitly to the left — which is what the dig
needs — and `bumpCounter` consumes that blank, which is what the loop's own
invariant wants.  So the counter must be excavated *between* the two, while the
guide still carries only `|xs 2|` marks.  The reservoir must nonetheless hold
`|xs 2| + 2` blanks, so the dig takes two extra steps in each direction rather
than one.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-- The excavation with `k` extra steps on each side. -/
theorem digRoundTrip_tapeK (k m : Nat) :
    ((moveDir HeadMove.right)^[k])
        (((moveDir HeadMove.right)^[m])
          (((moveDir HeadMove.left)^[m])
            (((moveDir HeadMove.left)^[k])
              (cellsTape [] ([] : List TapeSymbol))))) =
      cellsTape (List.replicate (m + k) TapeSymbol.blank) [] := by
  have h0 : ((moveDir HeadMove.left)^[k])
      (cellsTape [] ([] : List TapeSymbol)) =
      ⟨[], TapeSymbol.blank, List.replicate k TapeSymbol.blank⟩ := by
    have h := moveLeft_blanks 0 k
    simpa using h
  rw [h0, moveLeft_blanks k m]
  have h1 : ((moveDir HeadMove.right)^[m])
      (⟨[], TapeSymbol.blank, List.replicate (m + k) TapeSymbol.blank⟩ :
        Tape) =
      ⟨List.replicate m TapeSymbol.blank, TapeSymbol.blank,
        List.replicate k TapeSymbol.blank⟩ := by
    have h := moveRight_blanks k m 0
    simpa using h
  rw [h1]
  have h2 : ((moveDir HeadMove.right)^[k])
      (⟨List.replicate m TapeSymbol.blank, TapeSymbol.blank,
        List.replicate k TapeSymbol.blank⟩ : Tape) =
      ⟨List.replicate (m + k) TapeSymbol.blank, TapeSymbol.blank, []⟩ := by
    have h := moveRight_blanks 0 k m
    simpa using h
  rw [h2]
  rfl

/-- Excavate a reservoir two cells wider than the guide's tally. -/
def counterSetup2 (gd cnt : Fin tapes) :=
  (moveUpTo cnt 2 HeadMove.left).andThen fun _ =>
    (digRoundTrip gd cnt).andThen fun _ =>
      moveUpTo cnt 2 HeadMove.right

set_option maxHeartbeats 4000000 in
/-- **The reservoir, two wider.** -/
theorem counterSetup2_spec (gd cnt : Fin tapes) (hgc : gd ≠ cnt)
    (marks Lg Rg : List TapeSymbol) (T : Fin tapes → Tape)
    (hnb : ∀ x ∈ marks, x ≠ TapeSymbol.blank)
    (hg : T gd = cellsTape (TapeSymbol.blank :: Lg)
      (marks ++ TapeSymbol.blank :: Rg))
    (hc : T cnt = cellsTape [] []) :
    ∃ cost : Nat,
      HaltsExactly (counterSetup2 gd cnt)
        ((counterSetup2 gd cnt).startCfg T) cost true ∧
      (((counterSetup2 gd cnt).step^[cost])
        ((counterSetup2 gd cnt).startCfg T)).tape =
        Function.update T cnt
          (cellsTape (List.replicate (marks.length + 2) TapeSymbol.blank)
            []) := by
  classical
  have g1 := moveUpTo_spec cnt 2 HeadMove.left (by omega) T
  set T1 := Function.update T cnt
    (((moveDir HeadMove.left)^[2]) (T cnt)) with hT1
  have s1 : (((moveUpTo cnt 2 HeadMove.left).step^[2])
      ((moveUpTo cnt 2 HeadMove.left).startCfg T)).tape = T1 := by
    rw [moveUpTo_tape cnt 2 HeadMove.left (by omega) T, hT1]
  have hT1g : T1 gd = cellsTape (TapeSymbol.blank :: Lg)
      (marks ++ TapeSymbol.blank :: Rg) := by
    rw [hT1, Function.update_of_ne hgc]
    exact hg
  obtain ⟨c2, g2, s2⟩ := digRoundTrip_spec gd cnt hgc marks Lg Rg T1 hnb hT1g
  set T2 := Function.update T1 cnt
    (((moveDir HeadMove.right)^[marks.length])
      (((moveDir HeadMove.left)^[marks.length]) (T1 cnt))) with hT2
  have g3 := moveUpTo_spec cnt 2 HeadMove.right (by omega) T2
  have s3 : (((moveUpTo cnt 2 HeadMove.right).step^[2])
      ((moveUpTo cnt 2 HeadMove.right).startCfg T2)).tape =
      Function.update T2 cnt (((moveDir HeadMove.right)^[2]) (T2 cnt)) := by
    rw [moveUpTo_tape cnt 2 HeadMove.right (by omega) T2]
  have k2 := chainStepC g2 s2 g3
  have k1 := chainStepC g1 s1 k2.1
  refine ⟨_, k1.1, ?_⟩
  have hfin := k1.2
  rw [k2.2] at hfin
  have hfin' : ((counterSetup2 gd cnt).step^[_])
      ((counterSetup2 gd cnt).startCfg T) = _ := hfin
  rw [hfin']
  show (((moveUpTo cnt 2 HeadMove.right).step^[2])
    ((moveUpTo cnt 2 HeadMove.right).startCfg T2)).tape = _
  rw [s3]
  funext j
  by_cases hj : j = cnt
  · subst hj
    rw [Function.update_self, Function.update_self, hT2, Function.update_self,
      hT1, Function.update_self, hc]
    exact digRoundTrip_tapeK 2 marks.length
  · rw [Function.update_of_ne hj, Function.update_of_ne hj, hT2,
      Function.update_of_ne hj, hT1, Function.update_of_ne hj]

/-! ## The guide and the counter, together -/

/-- Tally the third input onto the guide, excavate the counter beside it, then
add the guide's last mark. -/
def guideSetup (src gd cnt : Fin tapes) :=
  (markBack src gd).andThen fun _ =>
    (counterSetup2 gd cnt).andThen fun _ =>
      bumpCounter gd

set_option maxHeartbeats 4000000 in
/-- **Guide and counter, ready for round zero.**  The guide carries one mark
per cell of the input plus one, head on the first; the counter is empty with a
reservoir one longer than the guide; the input is restored. -/
theorem guideSetup_spec (src gd cnt : Fin tapes)
    (hsg : src ≠ gd) (hgc : gd ≠ cnt) (hsc : src ≠ cnt)
    (x Ls Rs : List TapeSymbol) (T : Fin tapes → Tape)
    (hnb : ∀ c ∈ x, c ≠ TapeSymbol.blank)
    (hs : T src = cellsTape (TapeSymbol.blank :: Ls)
      (x ++ TapeSymbol.blank :: Rs))
    (hg : T gd = cellsTape [TapeSymbol.blank] [])
    (hc : T cnt = cellsTape [] []) :
    ∃ cost : Nat,
      HaltsExactly (guideSetup src gd cnt)
        ((guideSetup src gd cnt).startCfg T) cost true ∧
      (((guideSetup src gd cnt).step^[cost])
        ((guideSetup src gd cnt).startCfg T)).tape =
        Function.update (Function.update T cnt
          (cellsTape (List.replicate (x.length + 2) TapeSymbol.blank) []))
          gd (cellsTape []
            (List.replicate (x.length + 1) (TapeSymbol.bit true) ++
              [TapeSymbol.blank])) := by
  classical
  obtain ⟨c1, g1, s1⟩ := markBack_spec src gd hsg x Ls [] Rs []
    T hnb hs (by rw [hg])
  set T1 := Function.update (Function.update T src
    (cellsTape (TapeSymbol.blank :: Ls) (x ++ TapeSymbol.blank :: Rs))) gd
    (cellsTape [TapeSymbol.blank]
      (List.replicate x.length (TapeSymbol.bit true) ++
        (List.drop x.length ([] : List TapeSymbol)).headD TapeSymbol.blank ::
          (List.drop x.length ([] : List TapeSymbol)).tail)) with hT1
  have hT1g : T1 gd = cellsTape (TapeSymbol.blank :: [])
      (List.replicate x.length (TapeSymbol.bit true) ++
        TapeSymbol.blank :: []) := by
    rw [hT1, Function.update_self]
    simp
  have hT1c : T1 cnt = cellsTape [] [] := by
    rw [hT1, Function.update_of_ne (Ne.symm hgc),
      Function.update_of_ne (Ne.symm hsc)]
    exact hc
  have hmk : ∀ y ∈ List.replicate x.length (TapeSymbol.bit true),
      y ≠ TapeSymbol.blank := by
    intro y hy
    rw [List.eq_of_mem_replicate hy]
    simp
  obtain ⟨c2, g2, s2⟩ := counterSetup2_spec gd cnt hgc
    (List.replicate x.length (TapeSymbol.bit true)) [] [] T1 hmk hT1g hT1c
  set T2 := Function.update T1 cnt
    (cellsTape (List.replicate
      ((List.replicate x.length (TapeSymbol.bit true)).length + 2)
      TapeSymbol.blank) []) with hT2
  have hT2g : T2 gd = cellsTape (TapeSymbol.blank :: [])
      (List.replicate x.length (TapeSymbol.bit true) ++
        TapeSymbol.blank :: []) := by
    rw [hT2, Function.update_of_ne hgc]
    exact hT1g
  obtain ⟨g3, s3⟩ := bumpCounter_spec gd x.length [] [] T2 hT2g
  have k2 := chainStepC g2 s2 g3
  have k1 := chainStepC g1 s1 k2.1
  refine ⟨_, k1.1, ?_⟩
  have hfin := k1.2
  rw [k2.2] at hfin
  have hfin' : ((guideSetup src gd cnt).step^[_])
      ((guideSetup src gd cnt).startCfg T) = _ := hfin
  rw [hfin']
  show (((bumpCounter gd).step^[1 + 1 + 1])
    ((bumpCounter gd).startCfg T2)).tape = _
  rw [s3]
  funext j
  by_cases hj : j = gd
  · subst hj
    rw [Function.update_self, Function.update_self]
  · rw [Function.update_of_ne hj, Function.update_of_ne hj, hT2]
    by_cases hj2 : j = cnt
    · subst hj2
      rw [Function.update_self, Function.update_self]
      simp
    · rw [Function.update_of_ne hj2, Function.update_of_ne hj2, hT1,
        Function.update_of_ne hj]
      by_cases hj3 : j = src
      · subst hj3
        rw [Function.update_self]
        exact hs.symm
      · rw [Function.update_of_ne hj3]

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