Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_counter_setup

Definition

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

Definition code
import Definitions.Def_sgl_dig_left

/-!
# Setting the counter up

Three stages: step left off the tape's origin, walk out and back guided by the
guide's marks, step right again.  The net effect on a virgin scratch tape is to
leave the head exactly where it started with one blank per round behind it —
the reservoir every bump spends from.

Nothing is written at any point.  The blanks are not written blanks; they are
the cells the zipper materialises when the head walks past its own end, moved
into the left context by walking back.  That is the only way to obtain them,
since writing a blank onto a cell that is already blank changes nothing about
the representation.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-- Excavate the counter's reservoir, using the guide as the ruler. -/
def counterSetup (gd cnt : Fin tapes) :=
  (moveUpTo cnt 1 HeadMove.left).andThen fun _ =>
    (digRoundTrip gd cnt).andThen fun _ =>
      moveUpTo cnt 1 HeadMove.right

set_option maxHeartbeats 4000000 in
/-- **The reservoir, in place.**  From a virgin counter tape and a guide
carrying `marks`, the counter ends with `|marks| + 1` blanks to the left of its
head and the guide is untouched. -/
theorem counterSetup_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 (counterSetup gd cnt)
        ((counterSetup gd cnt).startCfg T) cost true ∧
      (((counterSetup gd cnt).step^[cost])
        ((counterSetup gd cnt).startCfg T)).tape =
        Function.update T cnt
          (cellsTape (List.replicate (marks.length + 1) TapeSymbol.blank) []) := by
  classical
  have g1 := moveUpTo_spec cnt 1 HeadMove.left (by omega) T
  set T1 := Function.update T cnt (moveDir HeadMove.left (T cnt)) with hT1
  have s1 : (((moveUpTo cnt 1 HeadMove.left).step^[1])
      ((moveUpTo cnt 1 HeadMove.left).startCfg T)).tape = T1 := by
    rw [moveUpTo_tape cnt 1 HeadMove.left (by omega) T, hT1,
      Function.iterate_one]
  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 1 HeadMove.right (by omega) T2
  have s3 : (((moveUpTo cnt 1 HeadMove.right).step^[1])
      ((moveUpTo cnt 1 HeadMove.right).startCfg T2)).tape =
      Function.update T2 cnt (moveDir HeadMove.right (T2 cnt)) := by
    rw [moveUpTo_tape cnt 1 HeadMove.right (by omega) T2, Function.iterate_one]
  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' : ((counterSetup gd cnt).step^[_])
      ((counterSetup gd cnt).startCfg T) = _ := hfin
  rw [hfin']
  show (((moveUpTo cnt 1 HeadMove.right).step^[1])
    ((moveUpTo cnt 1 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_tape 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]

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