Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

sgl_dig_left

Definition

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

Definition code
import Definitions.Def_sgl_offset_cost

/-!
# Digging a blank reservoir

The counter's left context must hold one blank per round: each bump spends one,
and a counter that runs out cannot be bumped again.  A freshly provisioned
scratch tape has *no* left context at all — the zipper is empty on that side —
so the reservoir has to be excavated before the loop starts.

Excavating it is a round trip.  Walking left off the end of a zipper
materialises a blank on the right, and walking back right pushes those blanks
into the left context, so `m` steps out and `m` steps back leaves the head where
it started with `m` blanks behind it.  Neither pass writes anything.

`moveUpTo` cannot do this — it is capped at twelve steps — so the walk is
guided by a tape that already carries `m` marks, exactly as `skipAhead` is.
`digRoundTrip` is `skipAhead` with its first pass reversed, and the guide's own
lemmas are direction-generic once the worker's direction is freed from the
guide's.
-/

namespace SipserGacsLautemann

variable {tapes : Nat}

/-! ## The guide's lemmas, with the worker's direction free -/

/-- One round of a guided walk, in `cellsTape` form, for any worker
direction. -/
theorem guidedStep_move (g w : Fin tapes) (hgw : g ≠ w) (dir : HeadMove)
    (T : Fin tapes → Tape) (a : TapeSymbol) (Lg Rg : List TapeSymbol)
    (hg : T g = cellsTape Lg (a :: Rg)) :
    (guidedStep g w dir none T) g = cellsTape (a :: Lg) Rg ∧
    (guidedStep g w dir none T) w = moveDir dir (T w) := by
  constructor
  · show (if g = g then moveDir HeadMove.right (T g) else _) = _
    rw [if_pos rfl, hg, cellsTape_moveRight]
  · show (if w = g then _ else if w = w then moveDir dir (T w) else _) = _
    rw [if_neg (fun h => hgw h.symm), if_pos rfl]

theorem guidedStep_move_iterate (g w : Fin tapes) (hgw : g ≠ w)
    (dir : HeadMove) :
    ∀ (marks : List TapeSymbol) (T : Fin tapes → Tape)
      (Lg Rg : List TapeSymbol),
      T g = cellsTape Lg (marks ++ Rg) →
      (((guidedStep g w dir none)^[marks.length]) T) g =
        cellsTape (marks.reverse ++ Lg) Rg ∧
      (((guidedStep g w dir none)^[marks.length]) T) w =
        ((moveDir dir)^[marks.length]) (T w) := by
  intro marks
  induction marks with
  | nil => intro T Lg Rg hg; simpa using hg
  | cons a marks ih =>
      intro T Lg Rg hg
      obtain ⟨h1, h2⟩ := guidedStep_move g w hgw dir T a Lg (marks ++ Rg)
        (by rw [hg]; rfl)
      obtain ⟨i1, i2⟩ := ih (guidedStep g w dir none T) (a :: Lg) Rg (by rw [h1])
      rw [List.length_cons, Function.iterate_succ_apply]
      refine ⟨by rw [i1]; congr 1; simp, ?_⟩
      rw [i2, h2, Function.iterate_succ_apply]

theorem guidedStep_move_marks (g w : Fin tapes) (hgw : g ≠ w)
    (dir : HeadMove) :
    ∀ (marks : List TapeSymbol) (T : Fin tapes → Tape)
      (Lg Rg : List TapeSymbol),
      (∀ c ∈ marks, c ≠ TapeSymbol.blank) →
      T g = cellsTape Lg (marks ++ Rg) →
      ∀ r, r < marks.length →
        (((((guidedStep g w dir none)^[r]) T) g).head ≠ TapeSymbol.blank) := by
  intro marks
  induction marks with
  | nil => intro _ _ _ _ _ r hr; simp at hr
  | cons a marks ih =>
      intro T Lg Rg hnb hg r hr
      cases r with
      | zero =>
          rw [Function.iterate_zero_apply, hg]
          exact hnb a (by simp)
      | succ r =>
          obtain ⟨h1, _⟩ := guidedStep_move g w hgw dir T a Lg (marks ++ Rg)
            (by rw [hg]; rfl)
          rw [Function.iterate_succ_apply]
          exact ih (guidedStep g w dir none T) (a :: Lg) Rg
            (fun c hc => hnb c (by simp [hc])) (by rw [h1])
            r (by simpa using hr)

/-! ## The machine -/

/-- Walk the worker `m` cells left and back, guided by `m` marks. -/
def digRoundTrip (g w : Fin tapes) :=
  (guidedWalk g w HeadMove.left none).andThen fun _ =>
    (rewindRun g).andThen fun _ =>
      (guidedWalk g w HeadMove.right none).andThen fun _ =>
        rewindRun g

set_option maxHeartbeats 4000000 in
/-- **The reservoir.**  Guided by `m` marks, the worker walks `m` cells left
and `m` cells back, and the guide is restored exactly. -/
theorem digRoundTrip_spec (g w : Fin tapes) (hgw : g ≠ w)
    (marks Lc Rc : List TapeSymbol) (T : Fin tapes → Tape)
    (hnb : ∀ x ∈ marks, x ≠ TapeSymbol.blank)
    (hc : T g = cellsTape (TapeSymbol.blank :: Lc)
      (marks ++ TapeSymbol.blank :: Rc)) :
    ∃ cost : Nat,
      HaltsExactly (digRoundTrip g w) ((digRoundTrip g w).startCfg T) cost
        true ∧
      (((digRoundTrip g w).step^[cost])
        ((digRoundTrip g w).startCfg T)).tape =
        Function.update T w
          (((moveDir HeadMove.right)^[marks.length])
            (((moveDir HeadMove.left)^[marks.length]) (T w))) := by
  classical
  obtain ⟨h1a, h1b⟩ := guidedStep_move_iterate g w hgw HeadMove.left marks T
    (TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc) (by rw [hc])
  obtain ⟨hW1, hW1t⟩ := guidedWalk_spec g w hgw HeadMove.left none
    marks.length T
    (guidedStep_move_marks g w hgw HeadMove.left marks T
      (TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc) hnb (by rw [hc]))
    (by rw [h1a]; rfl)
  set T1 := ((guidedStep g w HeadMove.left none)^[marks.length]) T with hT1
  have hT1c : T1 g = cellsTape (marks.reverse ++ TapeSymbol.blank :: Lc)
      (TapeSymbol.blank :: Rc) := h1a
  have hT1w : T1 w = ((moveDir HeadMove.left)^[marks.length]) (T w) := h1b
  obtain ⟨hR1, hR1t⟩ := rewindRun_spec g marks Lc Rc TapeSymbol.blank T1
    hnb (by rw [hT1c])
  set T2 := Function.update T1 g
    (cellsTape (TapeSymbol.blank :: Lc) (marks ++ TapeSymbol.blank :: Rc))
    with hT2
  have hT2c : T2 g = cellsTape (TapeSymbol.blank :: Lc)
      (marks ++ TapeSymbol.blank :: Rc) := by rw [hT2]; simp
  have hT2w : T2 w = ((moveDir HeadMove.left)^[marks.length]) (T w) := by
    rw [hT2, Function.update_of_ne (fun h => hgw h.symm)]
    exact hT1w
  obtain ⟨h2a, h2b⟩ := guidedStep_move_iterate g w hgw HeadMove.right marks T2
    (TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc) (by rw [hT2c])
  obtain ⟨hW2, hW2t⟩ := guidedWalk_spec g w hgw HeadMove.right none
    marks.length T2
    (guidedStep_move_marks g w hgw HeadMove.right marks T2
      (TapeSymbol.blank :: Lc) (TapeSymbol.blank :: Rc) hnb (by rw [hT2c]))
    (by rw [h2a]; rfl)
  set T3 := ((guidedStep g w HeadMove.right none)^[marks.length]) T2 with hT3
  have hT3c : T3 g = cellsTape (marks.reverse ++ TapeSymbol.blank :: Lc)
      (TapeSymbol.blank :: Rc) := h2a
  obtain ⟨hR2, hR2t⟩ := rewindRun_spec g marks Lc Rc TapeSymbol.blank T3
    hnb (by rw [hT3c])
  refine ⟨_, (chainStepC hW1 hW1t (chainStepC hR1 hR1t
    (chainStepC hW2 hW2t hR2).1).1).1, ?_⟩
  have hin2 := chainStepC hW2 hW2t hR2
  have hin1 := chainStepC hR1 hR1t hin2.1
  have hch := chainStepC hW1 hW1t hin1.1
  have hfin := hch.2
  rw [hin1.2, hin2.2] at hfin
  have hfin' : ((digRoundTrip g w).step^[_])
      ((digRoundTrip g w).startCfg T) = _ := hfin
  rw [hfin']
  show (((rewindRun g).step^[_]) ((rewindRun g).startCfg T3)).tape = _
  rw [hR2t]
  funext j
  by_cases hj : j = g
  · subst hj
    rw [Function.update_self, Function.update_of_ne hgw, hc]
  · rw [Function.update_of_ne hj]
    by_cases hj2 : j = w
    · subst hj2
      rw [Function.update_self, h2b, hT2w]
    · rw [Function.update_of_ne hj2, hT3,
        guidedStep_other g w HeadMove.right none marks.length T2 j hj hj2,
        hT2, Function.update_of_ne hj, hT1,
        guidedStep_other g w HeadMove.left none marks.length T j hj hj2]

/-! ## What the round trip does to a blank tape -/

/-- Walking left off the end materialises blanks on the right. -/
theorem moveLeft_blanks (j : Nat) : ∀ m : Nat,
    ((moveDir HeadMove.left)^[m])
        (⟨[], TapeSymbol.blank, List.replicate j TapeSymbol.blank⟩ : Tape) =
      ⟨[], TapeSymbol.blank, List.replicate (m + j) TapeSymbol.blank⟩ := by
  intro m
  induction m with
  | zero => simp
  | succ m ih =>
      rw [Function.iterate_succ_apply', ih]
      show (⟨[], TapeSymbol.blank,
        TapeSymbol.blank :: List.replicate (m + j) TapeSymbol.blank⟩ : Tape) = _
      rw [← List.replicate_succ]
      congr 2
      omega

/-- Walking back right pushes them into the left context. -/
theorem moveRight_blanks (j : Nat) : ∀ (m k : Nat),
    ((moveDir HeadMove.right)^[m])
        (⟨List.replicate k TapeSymbol.blank, TapeSymbol.blank,
          List.replicate (m + j) TapeSymbol.blank⟩ : Tape) =
      ⟨List.replicate (k + m) TapeSymbol.blank, TapeSymbol.blank,
        List.replicate j TapeSymbol.blank⟩ := by
  intro m
  induction m with
  | zero => intro k; simp
  | succ m ih =>
      intro k
      rw [Function.iterate_succ_apply]
      have hstep : moveDir HeadMove.right
          (⟨List.replicate k TapeSymbol.blank, TapeSymbol.blank,
            List.replicate (m + 1 + j) TapeSymbol.blank⟩ : Tape) =
          ⟨List.replicate (k + 1) TapeSymbol.blank, TapeSymbol.blank,
            List.replicate (m + j) TapeSymbol.blank⟩ := by
        rw [show m + 1 + j = (m + j) + 1 by omega, List.replicate_succ,
          List.replicate_succ]
        rfl
      rw [hstep, ih (k + 1)]
      congr 2
      omega

/-- **The excavation, as a tape equation.**  One step left, a round trip of
`m`, and one step right leave the head where it started with `m + 1` blanks
behind it. -/
theorem digRoundTrip_tape (m : Nat) :
    moveDir HeadMove.right
        (((moveDir HeadMove.right)^[m])
          (((moveDir HeadMove.left)^[m])
            (moveDir HeadMove.left (cellsTape [] ([] : List TapeSymbol))))) =
      cellsTape (List.replicate (m + 1) TapeSymbol.blank) [] := by
  have h0 : moveDir HeadMove.left (cellsTape [] ([] : List TapeSymbol)) =
      ⟨[], TapeSymbol.blank, List.replicate 1 TapeSymbol.blank⟩ := rfl
  rw [h0, moveLeft_blanks 1 m]
  have h1 : ((moveDir HeadMove.right)^[m])
      (⟨[], TapeSymbol.blank, List.replicate (m + 1) TapeSymbol.blank⟩ :
        Tape) =
      ⟨List.replicate m TapeSymbol.blank, TapeSymbol.blank,
        [TapeSymbol.blank]⟩ := by
    have h := moveRight_blanks 1 m 0
    simpa using h
  rw [h1]
  show (⟨TapeSymbol.blank :: List.replicate m TapeSymbol.blank,
    TapeSymbol.blank, []⟩ : Tape) = _
  rw [← List.replicate_succ]
  rfl

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